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

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

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

Ответить
Тоня
Популярный автор
Популярный автор
Сообщения: 2526
Зарегистрирован: 29 июн 2005, 21:45
Пол: Женский

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

Сообщение Тоня »

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

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

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

Сообщение Dendr »

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 »

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

Пусть 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-й карточки)

Ответ: нет.

Тоня
Популярный автор
Популярный автор
Сообщения: 2526
Зарегистрирован: 29 июн 2005, 21:45
Пол: Женский

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

Сообщение Тоня »

Dendr писал(а): Ответ: нет.
Да (в смысле ответ - нет)

Ответить

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