Задача на матиндукцию (последняя из ЕГЭ)

[mr.vopros]

Добрый вечер! Есть решение, хотелось бы разобраться с ним, помогите, пожалуйста!
Задача такая:

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

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

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

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

В оффтопе оригнал решения:

(Оффтоп)

Я большую часть решения понял, кроме двух фраз:
1)

Цитата:

Ясно, что в $m-2$-ой строчке будет написано несколько групп одинаковых чисел, по $a$ в каждой группе, причем числа из разных групп различны. Отсюда вытекает, что $b$ делится на $a$

Допустим у нас есть несколько групп чисел, по $a$ в каждой, причем различных (кстати, а если $a>500$)?

$c_1, c_2, c_3,..., c_a, d_1,d_2,...,d_a, e_1,e_2,...e_a,....$

Но как отсюда следует, что $b$ делится на $a$?

2) Почему обязательно найдется $b>a$ (в самом начале рассуждения)?

[mihaild]

mr.vopros в сообщении #1564879 писал(а):

Но как отсюда следует, что $b$ делится на $a$?

$b$ - это общее число чисел во всех группах, а размер каждой группы делится на $a$, значит и общее количество чисел во всех группах делится на $a$.

mr.vopros в сообщении #1564879 писал(а):

Почему обязательно найдется $b>a$ (в самом начале рассуждения)?

Это, конечно, нужно доказывать. Покажите, что если число во второй строчке или ниже отличается от написанного под ним, то число ниже всегда больше. Для этого воспользуйтесь тем, что если во второй или более нижней строчке вообще присутствует какое-то число $x$, то оно в ней присутствует не менее $x$ раз (и этот факт тоже докажите).

[mr.vopros]

mihaild в сообщении #1564881 писал(а):

Это, конечно, нужно доказывать. Покажите, что если число во второй строчке или ниже отличается от написанного под ним, то число ниже всегда больше. Для этого воспользуйтесь тем, что если во второй или более нижней строчке вообще присутствует какое-то число $x$, то оно в ней присутствует не менее $x$ раз (и этот факт тоже докажите).

Спасибо большоее. Пусть у нас были числа в первой строчке:

$1,....,1(k_1 \text{раз}),2,2,....2(k_2 \text{раз}), ..., n,n, .... , n (k_n \text{раз})$ при этом $k_i$ может быть нулем, а $\displaystile\sum\limits_{i=1}^{n}k_i=1000$

Вторая строчка, в которую мы не будем записывать $k_i=0$:

$k_1, k_1, k_1, ..., k_1 (k_1 \text{раз}),k_2, k_2,...k_2(k_2 \text{раз}), ..., k_n,k_n, .... , k_n (k_n \text{раз})$

Если среди $k_1, k_2, ...,k_n$ нет одинаковых, то дальше именно такая вторая строчка будет повторяться до бесконечности.

Если среди найдутся одинаковые, например $k_1=k_2$, то обозначим $k=k_1=k_2$ и строчкой ниже будет вот что

$k, k, ..., k (2k \text{раз}),k_3,k_3,....k_3(k_3 \text{раз}), ..., k_n,k_n, k_n, .... , k_n (k_n \text{раз})$

Назовем числа, которые в строчке $i-1$ не совпадали, а в строчке $i$ совпали - удачными $i$-го уровня, а соответсвующие им строчкой выше - на пути к уровню $i$.

Тогда пусть $t$ - количество попарно различных чисел, которых можно отнести к категории "на пути к уровню $2$". А буквой $r$ - количество раз, которое каждое из этих попарно различных чисел встречается в строчке $1$. Во второй строчке, под ними будет тогда написано число $r$ ровно $t\cdot r$ раз (то есть именно столько удачных второго уровня. А в третьей строчке $t\cdot r$ как минимум $t\cdot r$ раз. Получается, что после второй строчки каждое из чисел может остаться таким же или кратно увеличиться. Верно ли это, подскажите, пожалуйста?! Можно ли сказать, что я тогда ответил и на Ваши вопросы, и на свои (с Вашей помощью)?