|
|
 |
Условие
Изначально на стол положили 100 карточек, на каждой из которых записано по натуральному числу; при этом было ровно 43 карточки с нечётными числами. Затем каждую минуту проводилась следующая процедура. Для каждых трёх карточек, лежащих на столе, вычислялось произведение записанных на них чисел, все эти произведения складывались, и полученное число записывалось на новую карточку, которая добавлялась к лежащим на столе. Через год после начала процесса выяснилось, что на столе есть карточка с числом, кратным 210000. Докажите, что число, кратное 210000, было на одной из карточек уже через день после начала.
Решение
Если в некоторый момент среди чисел на карточках есть ровно k нечётных, то среди произведений троек чисел ровно нечётных; поэтому число на очередной добавляемой карточке будет нечётным тогда и только тогда, когда
нечётно (причём k в эту минуту увеличится на единицу).
Заметим, что число нечётно, а число
чётно. Значит, в первую минуту добавится нечётное число, а дальше будут добавляться только чётные. Итак, после первой минуты среди чисел на карточках всегда будет ровно 44 нечётных.
Рассмотрим числа на карточках после n минут. Пусть Tn – сумма всех произведений троек этих чисел, а Dn – сумма всех произведений пар этих чисел. Число Tn+1 отличается от Tn прибавлением всех произведений троек чисел, среди которых есть только что добавленное, то есть прибавлением DnTn:
Tn+1 = Tn + DnTn = Tn(1 + Dn). Заметим, что при n > 1. Значит, при n > 1 число 1 + Dn нечётно, и степень двойки, на которую делится Tn+1, равна степени двойки, на которую делится Tn.
Итак, после первой минуты степень двойки, на которую делится добавляемое число Tn, всегда равна степени двойки, на которую делится T1. Значит, если бы после второй минуты на карточках не было числа, кратного 210000, то и впоследствии такого числа бы не появилось.
Замечания
Ср. с задачей 66032.
