98 БАЛЛОВ! Пожалуйста, объясните, как решать задачи такого вида [еще приведите решение этой задачи]. Заранее спасибо!
Студенты 5 раз сдавали зачет (не сумевшие сдать зачет приходили на следующий день). Каждый раз успешно сдавала зачет треть всех пришедших студентов и еще треть студента. Каково наименьшее возможное число студентов, так и не сдавших зачет? Сколько вообще могло быть студентов?
Ответы
Пусть студенты сдавали зачёт n раз. Разобьём студентов на несколько групп по 3ⁿ студентов в каждой и "остаток". На каждом зачёте из группы зачёт будет успешно сдавать только треть студентов, а "ещё треть студента" будет каждый раз браться из "остатка". Заметим, что теперь имеет значение только количество студентов в остатке. Если оно будет целым после каждого зачёта, то и всё количество студентов будет целым.
Методом Математической Индукции докажем, что условие будет выполнено только если в остатке было 3ⁿ - 1 студентов. База (n = 1) очевидна. Теперь выполним переход (от n к n+1). Так как нам известно, что сдать зачёт n раз студенты могли только при наличии 3ⁿ - 1 студентов в остатке, то n + 1 раз сдать зачёт они могли только в случае 3ⁿ - 1, 2 * 3ⁿ - 1 и 3^(n+1) - 1 студентов в остатке. Первый не подходит, так как по предположению индукции сдать n зачётов не получится, если в остатке меньше 3ⁿ - 1 студента (предполагается, что один зачёт они уже сдали). Во втором случае проведём один зачёт:
(2 * 3ⁿ - 1) * 2/3 - 1/3 = 4 * 3^(n-1) - 1 ≡ 3^(n-1)-1 (mod 3ⁿ)
По предположению индукции, в остатке не требуемое количество студентов, следовательно, ещё n зачётов провести не удастся.
В третьем случае тоже проведём один зачёт:
(3^(n+1) - 1) * 2/3 - 1/3 = 2 * 3ⁿ - 1 ≡ 3ⁿ - 1 (mod 3ⁿ)
А здесь по предположению индукции провести n зачётов удастся. Переход доказан.
Следовательно, для проведения n зачётов изначально должно было быть k * 3ⁿ - 1 студентов.
Теперь посчитаем количество студентов, так и не сдавших зачёт, из k * 3ⁿ - 1 студентов. В каждой группе зачёт не сдаст 2ⁿ студентов (так как на каждом зачёте количество студентов в каждой из групп умножается на 2/3). В остатке же останется 2ⁿ - 1 студент, так как после каждого зачёта сохраняется слагаемое "-1". Итак, осталось k * 2ⁿ - 1 студентов. Подставим k = 1 и n = 5 - получим ответ исходной задачи, 31.
Ответ: 31 (первый вопрос).
Предлагаю не самый рациональный и быстрый, но альтернативный способ решения.
