|
|
 |
Условие
Саша написал на доске ненулевую цифру и приписывает к ней справа
по одной ненулевой цифре, пока не выпишет миллион цифр. Докажите,
что на доске не более 100 раз был написан точный квадрат.
Решение
Рассмотрим отдельно числа из нечетного и из четного числа
знаков. Пусть x12, x22, .. – встретившиеся на доске
квадраты из четного количества знаков, и в их записи содержится соответственно
2n1, 2n2, .. (n1<n2<..) цифр. Аналогично, пусть y12,
y22, .. – встретившиеся на доске квадраты из нечетного количества
знаков, и в их записи содержится соответственно 2m1-1, 2m2-1, ..
(m1<m2<..) цифр.
Число xk2 содержит nk цифр и не оканчивается на 0, поэтому
xk2> 102nk-1 , откуда xk>10nk-1 . Число xk+12
получается из xk приписыванием некоторого четного количества –
обозначим его 2a – ненулевых цифр.
Поэтому 102axk2<xk+12<102axk2+102a .
Из левого неравенства получаем
10a xk+1 xk+1 , следовательно,
102axk2+2· 10a xk+1
xk+12<102axk2+102a , откуда
2·10axk+1<102a , т.е. xk<10a .
Из этого неравенства следует, что xk содержит не более a цифр, т.е.
nk a , тогда из неравенства 10axk+1
xk+1 следует
a+nk
nk+1 , откуда 2nk
nk+1 .
Аналогичное рассуждение применимо к последовательности {yk} :
yk+12 получается приписыванием к yk2 2a цифр, yk<10a ,
и a mk , т.е. mk+1
2mk . Теперь заметим, что
в каждой из последовательностей mk и nk меньше 50 членов (так
как m1, n1
1 и m50 и n50 должны быть не меньше,
чем 250>1000000 ).
Итак, всего квадратов на доске окажется не более 100.
