Maths Olympiad Prep

Library / /19 of 25

Combinatorics Difficulty 6.8 National olympiad Prove it Russia

Initially, we put 100 cards on a table, each containing a positive integer. Exactly 28 of these cards contain odd numbers. Then, on each minute the following operation has been performed. We compute the product of numbers on every set of 12 cards on the table, add up all these products, write this number onto a new card and put this card onto the table. Is it possible to choose initial 100 numbers so that for every positive integer dd the table will eventually contain some card with a number divisible by 2d2^d? (I. Bogdanov)

Изначально на стол кладут 100 карточек, на каждой из которых написано положительное целое число. Ровно на 28 из этих карточек написаны нечётные числа. Затем каждую минуту выполняют следующую операцию: вычисляют произведение чисел на каждой из 12-карточных подмножеств карточек, складывают все эти произведения, записывают это число на новую карточку и кладут её на стол. Можно ли выбрать начальные 100 чисел так, чтобы для любого натурального dd на столе в какой-то момент появилась карточка с числом, делящимся на 2d2^d?

Solution

Answer. No.
If the table contains kk odd numbers, then the parity of a new one coincides with the parity of (k12)\binom{k}{12}; so, on the first four minutes kk increases by 1, and then it is always equal to 32. Consider any n4n \ge 4. Let EnE_n (TnT_n) be the sum of products of all 11-tuples (12-tuples) of the numbers. En(3211)0(mod2)E_n \equiv \binom{32}{11} \equiv 0 \pmod{2} for n4n \ge 4. The new number will be TnEnT_n E_n, so Tn+1=Tn(1+En)T_{n+1} = T_n(1+E_n), and the power of 2 in its expansion is the same as that of TnT_n. Choosing dd so that 2d2^d is greater than T4T_4, we obtain that no TnT_n will be divisible by 2d2^d.

Ответ. Нет, нельзя.
Если в некоторый момент среди чисел на карточках есть ровно kk нечётных, то среди произведений чисел по 12 ровно C12kC_{12}^k нечётных; поэтому число на очередной добавляемой карточке будет нечётным ровно тогда, когда C12kC_{12}^k нечётно (и тогда kk в эту минуту увеличится на 1).
Нетрудно заметить, что число C2812C_{28}^{12} нечётно (это следует из того, что степени двойки, входящие в 28271728 \cdot 27 \cdots 17 и 1211112 \cdot 11 \cdots 1, равны). Далее, поскольку C28+t12=(28+1)(28+2)(28+t)(16+1)(16+2)(16+t)C2812C_{28+t}^{12} = \frac{(28+1)(28+2)\cdots(28+t)}{(16+1)(16+2)\cdots(16+t)} \cdot C_{28}^{12}, получаем, что наименьшее tt, при котором C28+t12C_{28+t}^{12} чётно, равно 4.
Итак, количество нечётных чисел на карточках будет расти, пока не достигнет 32 (на 4-й минуте), а после этого на карточках всегда будет ровно 32 нечётных числа.
Рассмотрим числа на карточках после n4n \ge 4 минут. Пусть TnT_n — сумма всех произведений 12 из этих чисел, а EnE_n — сумма всех произведений 11 из этих чисел. Число Tn+1T_{n+1} отличается от TnT_n прибавлением всех произведений по 12 чисел, среди которых есть только что добавленное, то есть прибавлением TnEnT_n E_n; итак, Tn+1=Tn+EnTn=Tn(1+En)T_{n+1} = T_n + E_n T_n = T_n(1+E_n). Заметим при этом, что En=C3211(mod2)E_n = C_{32}^{11} \pmod{2} при n4n \ge 4, а число C3211=1221C3212C_{32}^{11} = \frac{12}{21} \cdot C_{32}^{12} чётно. Значит, при n4n \ge 4 число 1+En1+E_n нечётно, и степень двойки, на которую делится Tn+1T_{n+1}, равна степени двойки, на которую делится TnT_n.
Выберем теперь dd так, чтобы после пятой минуты ни одно из чисел на карточках не делилось на 2d2^d; в частности, только что добавленное число T4T_4 также не будет делиться на 2d2^d. Значит, и все числа T5,T6,T_5, T_6, \dots не будут делиться на 2d2^d, а это в точности числа, написанные на карточках, добавляемых после пятой минуты. Итак, на карточках никогда не появится числа, делящегося на 2d2^d.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.