Задача8 «Карточки» (Олимпиада школьников-2017)

Логические задачи

Модераторы: Азарапетыч, Администрация

Задача8 «Карточки» (Олимпиада школьников-2017)

Сообщение Тоня » 01 фев 2017, 22:56

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

Re: Задача8 «Карточки» (Олимпиада школьников-2017)

Сообщение Dendr » 02 фев 2017, 06:43

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.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Задача8 «Карточки» (Олимпиада школьников-2017)

Сообщение Dendr » 02 фев 2017, 08:51

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

Пусть 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
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Задача8 «Карточки» (Олимпиада школьников-2017)

Сообщение Тоня » 02 фев 2017, 18:07

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

Да (в смысле ответ - нет)
Тоня
Популярный автор
Популярный автор
 
Сообщения: 1597
Зарегистрирован: 29 июн 2005, 21:45


Вернуться в Задачки

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron