Разделы 
Дополнительно
Задача по математике - 3742
2019-06-16 
В строчку подряд написано 1000 чисел. Под ней пишется вторая строчка чисел по следующему правилу: под каждым числом а первой строчки выписывается натуральное число, указывающее, сколько раз а встречается в первой строчке. Из второй строчки таким же образом получается третья: под каждым числом $b$ второй строчки выписывается натуральное число, указывающее, сколько раз $b$ встречается во второй строчке. Затем из третьей строчки так же строится четвертая, из четвертой - пятая и так далее.
а) Докажите, что некоторая строчка совпадает со следующей.
б) Более того, докажите, что 11-я строчка совпадает с 12-й.
в) Приведите пример такой первоначальной строчки, для которой 10-я строчка не совпадает с 11-й.
Решение:
Решение задачи а) вытекает из таких двух соображений: (1) под каждым числом $a$ в $m$-й строчке ($m \geq 2$) написано число, не меньшее $a$; (2) каждое из этих чисел не превосходит 1000. Для решения б) нужно еще учесть, что если число $a$ в $m$-й строчке ($m \geq 2$) строго меньше стоящего под ним числа $b$, то $b \geq 2a$ несколько групп по $a$ чисел (каждая группа стоит под равными числами) объединяются в одну группу из $b$ чисел; отсюда по индукции следует, что в такой ситуации $b \geq 2^{m-1}$. Но $2^{m-1} \leq 1000$ лишь при $m \leq 10$. Пример последовательности, для которой 10-я строчка не совпадает с 11-й:
$0, 1, 2, 2, 4, 4, 4, 4, \underbrace{8, 8, \cdots, 8}_{5} \cdots, \underbrace{256, \cdots, 256}_{256}, \underbrace{488, \cdots, 488}_{488}$.
Вот как выглядят последовательные ее преобразования:
2 $1, 1, 2, 2, 4, \cdots, 4, 8, \cdots, 8 , \cdots, 256, \cdots, 256, 488, \cdots, 488$
3 $2, 2, 2, 2, 4, \cdots, 4 , 8, \cdots, 8 , \cdots, 256, \cdots, 256, 488, \cdots, 488$
$\cdots$
10 $255, 256, \cdots, 256, 488, \cdots, 488$
11 $512, 512, \cdots, 512, 488, \cdots, 488$.
Аналогично для последовательности из $n$ чисел, где $2^{k-1} \leq n < 2^k$, можно доказать, что $(k + 2)$ -я строка будет совпадать с $(k + 1)$-й, но $(k + 1)$-я еще может не совпадать с $k$-й.
В строчку подряд написано 1000 чисел. Под ней пишется вторая строчка чисел по следующему правилу: под каждым числом а первой строчки выписывается натуральное число, указывающее, сколько раз а встречается в первой строчке. Из второй строчки таким же образом получается третья: под каждым числом $b$ второй строчки выписывается натуральное число, указывающее, сколько раз $b$ встречается во второй строчке. Затем из третьей строчки так же строится четвертая, из четвертой - пятая и так далее.
а) Докажите, что некоторая строчка совпадает со следующей.
б) Более того, докажите, что 11-я строчка совпадает с 12-й.
в) Приведите пример такой первоначальной строчки, для которой 10-я строчка не совпадает с 11-й.
Решение:
Решение задачи а) вытекает из таких двух соображений: (1) под каждым числом $a$ в $m$-й строчке ($m \geq 2$) написано число, не меньшее $a$; (2) каждое из этих чисел не превосходит 1000. Для решения б) нужно еще учесть, что если число $a$ в $m$-й строчке ($m \geq 2$) строго меньше стоящего под ним числа $b$, то $b \geq 2a$ несколько групп по $a$ чисел (каждая группа стоит под равными числами) объединяются в одну группу из $b$ чисел; отсюда по индукции следует, что в такой ситуации $b \geq 2^{m-1}$. Но $2^{m-1} \leq 1000$ лишь при $m \leq 10$. Пример последовательности, для которой 10-я строчка не совпадает с 11-й:
$0, 1, 2, 2, 4, 4, 4, 4, \underbrace{8, 8, \cdots, 8}_{5} \cdots, \underbrace{256, \cdots, 256}_{256}, \underbrace{488, \cdots, 488}_{488}$.
Вот как выглядят последовательные ее преобразования:
2 $1, 1, 2, 2, 4, \cdots, 4, 8, \cdots, 8 , \cdots, 256, \cdots, 256, 488, \cdots, 488$
3 $2, 2, 2, 2, 4, \cdots, 4 , 8, \cdots, 8 , \cdots, 256, \cdots, 256, 488, \cdots, 488$
$\cdots$
10 $255, 256, \cdots, 256, 488, \cdots, 488$
11 $512, 512, \cdots, 512, 488, \cdots, 488$.
Аналогично для последовательности из $n$ чисел, где $2^{k-1} \leq n < 2^k$, можно доказать, что $(k + 2)$ -я строка будет совпадать с $(k + 1)$-й, но $(k + 1)$-я еще может не совпадать с $k$-й.
