Задача 110076

Темы:    [ Десятичная система счисления ] [ Перебор случаев ] [ Последовательности (прочее) ]

Сложность: 5- Классы: 9,10,11

Условие

Автор: Голованов А.С.

Саша написал на доске ненулевую цифру и приписывает к ней справа по одной ненулевой цифре, пока не выпишет миллион цифр. Докажите, что на доске не более 100 раз был написан точный квадрат.

Решение

Рассмотрим отдельно числа из нечетного и из четного числа знаков. Пусть x₁², x₂², .. – встретившиеся на доске квадраты из четного количества знаков, и в их записи содержится соответственно 2n₁, 2n₂, .. (n₁<n₂<..) цифр. Аналогично, пусть y₁², y₂², .. – встретившиеся на доске квадраты из нечетного количества знаков, и в их записи содержится соответственно 2m₁-1, 2m₂-1, .. (m₁<m₂<..) цифр.

Число x_k2 содержит n_k цифр и не оканчивается на 0, поэтому x_k²> 102n_k-1 , откуда x_k>10^n_k-1 . Число x_k+1² получается из x_k приписыванием некоторого четного количества – обозначим его 2a – ненулевых цифр.

Поэтому 102ax_k²<x_k+1²<102ax_k²+102a . Из левого неравенства получаем 10^a x_k+1 x_k+1 , следовательно, 102ax_k²+2· 10^a x_k+1 x_k+12<102ax_k²+102a , откуда 2·10^ax_k+1<102a , т.е. x_k<10^a .

Из этого неравенства следует, что x_k содержит не более a цифр, т.е. n_k a , тогда из неравенства 10^ax_k+1 x_k+1 следует a+n_k n_k+1 , откуда 2n_k n_k+1 .

Аналогичное рассуждение применимо к последовательности {y_k} : y_k+1² получается приписыванием к y_k² 2a цифр, y_k<10^a , и a m_k , т.е. m_k+1 2m_k . Теперь заметим, что в каждой из последовательностей m_k и n_k меньше 50 членов (так как m₁, n₁ 1 и m50 и n50 должны быть не меньше, чем 250>1000000 ).

Итак, всего квадратов на доске окажется не более 100.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2001
Этап
Вариант	4
Класс
Класс	9
задача
Номер	01.4.9.8