Задача М409‍‍‍

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

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

в) Предыдущие рассуждения подсказывают пример:$$ \colsep{3pt}{\begin{array}{rrrrrrrrrrrrrrr} 0,&1,&2,&2,&4,&4,&4,&4,&{\ldots},&255,&{\ldots},&256,&488,&{\ldots},&488;\\ 1,&1,&2,&2,&4,&4,&4,&4,&{\ldots},&256,&{\ldots},&256,&488,&{\ldots},&488;\\ 2,&2,&2,&2,&4,&4,&4,&4,&{\ldots},&256,&{\ldots},&256,&488,&{\ldots},&488;\\ 4,&4,&4,&4,&4,&4,&4,&4,&{\ldots},&256,&{\ldots},&256,&488,&{\ldots},&488;\\ &&&&&&&&&&&&&&\mathllap{.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\enspace}\\ 256‚&&&&&&&&&&\mathllap{.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.},&256,&488,&{\ldots},&488;\\ 512‚&&&&&&&&&&\mathllap{.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.},&512,&488,&{\ldots},&488\hphantom; \end{array}} $$

(в первой строчке 0 и 1 встречаются по одному разу, 2 — два раза, 4 — четыре раза, 8 — восемь раз, $\ldots$‍,‍ 256 — 256 раз, 488 встречается 488 раз; в 11-й строчке встречается 512 раз число 512 и 488 раз число 488).

С нашей задачей связано интересное наблюдение. Возьмём какой-нибудь осмысленный текст, записанный буквами русского (можно и любого другого) алфавита. Рядом с каждой буквой напишем, сколько раз она повторяется в этом тексте, а дальше будем составлять таблицу так, как мы это делали раньше. В примере, приведённом на рисунке 8, пятый столбец уже совпадает с предыдущим: последним оказался четвёртый числовой столбец. Оказывается, для различных по содержанию и по длине осмысленных текстов количество неповторяющихся числовых столбцов нe бывает меньше двух и больше четырёх — примеры с одним или пятью или большим числом столбцов неизвестны. Примеры текстов с четырьмя неповторяющимися столбцами (наш пример) очень редки. Разумеется, можно найти такой набор повторяющихся букв, чтобы последним числовым столбцом в таблице оказался, скажем, десятый. Из этого набора букв можно даже составить слова, использовав все буквы; но составить осмысленный текст пока не удавалось. Почему это так, мы не знаем. Пока это только любопытное наблюдение. Попробуйте найти или составить такой осмысленный текст, чтобы в соответствующей таблице последним числовым столбцом оказался первый или пятый. Наверное, первая задача легче: ведь требование очень просто — различные буквы должны встречаться в тексте различное число раз.