danetka.ru

Изначально на стол кладут 100 карточек, на каждой из которых записано по натуральному числу; при этом среди них ровно 28 карточек с нечётными числами. Затем каждую минуту проводится следующая процедура. Для каждых 12 карточек, лежащих на столе, вычисляется произведение записанных на них чисел, все эти произведения складываются, и полученное число записывается на новую карточку, которая добавляется к лежащим на столе. Можно ли выбрать исходные 100 чисел так, чтобы для любого натурального d на столе рано или поздно появится карточка с числом, делящимся на "2 в степени d" ? (простите, тут не получается надстрочный шрифт поставить)

C(28,12) - нечетное. Поэтому на 101-й карточке запишется нечетное число.
Аналогично рассуждая, выясним, что на карточках 102, 103, 104 также нечетные, а на 105 и всех последующих - четные.

При этом, (назову это Леммой), число a_(n+1) делится на a_n. Следовательно, за d+4 хода мы гарантированно найдем число, делящееся га 2^d.

Доказательство Леммы: a_(n+1) равно сумме по-12 произведений всех записанных на доске чисел, при этом их (произведения) можно разделить на две группы: без участия a_n, и с ним. Первая сумма равна a_n. Во второй мы можем вынести его за скобку. Полная сумма делится на него. QED.

Ох. Нет, конечно. Зря без записи решал.

Пусть P(n,k) - сумма всех возможных произведений в комбинациях по k из n чисел.
Тогда a_n=P(n,12)
Но a_(n+1)=P(n+1,12)=P(n,12)+a_n*P(n,11)=a_n*(1+P(n,11))

Четность определяется числом нечетных чисел, точнее, количеством комбинаций. То есть вместо n можно писать здесь nodd, которое равно с некоторого момента 32, еще проще число комбинаций.

Так как C(32,11) четное, то после некоторого момента новое число равно предыдущему помножить на нечетное число.

Таким образом, "глубина" четности всех новых чисел равна глубине первого четного числа. (со 105-й карточки)

Ответ: нет.

Dendr писал(а): Ответ: нет.

Да (в смысле ответ - нет)