Задания
Версия для печати и копирования в MS Word
Тип 18 № 505663

В строку подряд написано 1000 чисел. Под каждым числом a первой строки напишем число, указывающее, сколько раз число a встречается в первой строке. Из полученной таким образом второй строки аналогично получаем третью: под каждым числом второй строки пишем, сколько раз оно встречается во второй строке. Затем из третьей строки так же получаем четвёртую, из четвёртой — пятую, и так далее.

а) Докажите, что некоторая строчка совпадает со следующей.

б) Докажите, что 11‐я строка совпадает с 12‐й.

в) Приведите пример такой первоначальной строчки, для которой 10‐я строка не совпадает с 11‐й.

Спрятать решение

Решение.

а) Очевидно, что начиная со второй строчки, все числа в таблице не больше 1000. Кроме того, каждое число не больше написанного под ним. Поэтому сумма чисел в третьей строчке не меньше, чем во второй и т. д., и каждая из этих сумм не больше миллиона. Следовательно, поскольку все время суммы возрастать не могут, в каких-то соседних строчках суммы совпадут, а тогда совпадут и сами строчки.

б) Докажем, что если в m-ой строчке при m\geqslant2, число отлично от написанного над ним, то оно не меньше, чем 2 в степени (m минус 2) . Действительно, для m=2 это очевидно, так как все числа второй строки натуральные. Пусть это уже проверено для всех строк с номерами, меньшими m. Пусть в m минус 1-ой строчке написано число а, а под ним написано число b, большее а. Тогда в m минус 2-ой строчке написано b чисел, равных а. Ясно, что в m минус 2-ой строчке будет написано несколько групп одинаковых чисел, по а в каждой группе, причем числа из разных групп различны. Отсюда вытекает, что b делится на а, то есть b\geqslant2a. Кроме того, по крайней мере одно из чисел в этих группах отличается от а, а значит, по предположению индукции a\geqslant2 в степени ((m минус 1) минус 2) . Итак, b\geqslant2a\geqslant2 в степени (m минус 2) . Наше утверждение доказано по индукции для всех m\geqslant2. Если предположить, что 11-я строчка отлична от 12-й, то какое-то число в 12-й строчке будет больше, чем 2 в степени (12 минус 2) =1024 больше 1000, что невозможно.

в) Приведем такой пример:

0, 1, 2, 2, 4, 4, 4, 4, …, 256, …, 256, 488, …, 488

1, 1, 2, 2, 4, 4, 4, 4, …, 256, …, 256, 488, …, 488

2, 2, 2, 2, 4, 4, 4, 4, …, 256, …, 256, 488, …, 488

4, 4, 4, 4, 4, 4, 4, 4, …, 256, …, 256, 488, …, 488

…………………………………………………………….

256, ……………………………., 256, 488, …, 488

1 512, ……………………………., 512, 488, …, 488

В первой строчке 0 и 1 встречаются по одному разу, 2 — два раза, 4 — четыре раза, 8 — восемь раз, …., 256 — 256 раз, 488 — встречается 488 раз, в 11 строчке встречается 512 раз число 512 и 488 раз число 488.

Спрятать критерии
Критерии проверки:

Критерии оценивания выполнения заданияБаллы
Верно получены все перечисленные (см. критерий на 1 балл) результаты.4
Верно получены три из перечисленных (см. критерий на 1 балл) результатов.3
Верно получены два из перечисленных (см. критерий на 1 балл) результатов.2
Верно получен один из следующий результатов:

— обоснованное решение в п. а;

— пример в п. б;

— искомая оценка в п. в;

— пример в п. в, обеспечивающий точность предыдущей оценки.

1
Решение не соответствует ни одному из критериев, перечисленных выше.0
Максимальный балл4
Источник: А. Ларин: Тренировочный вариант № 51.
Классификатор алгебры: Последовательности и прогрессии