Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела теория чисел
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#79762

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

Показать доказательство

Рассмотрим отдельно числа из нечетного и из четного числа знаков.

Пусть 2  2
x1,x2,...  — встретившиеся на доске квадраты из четного количества знаков, и в их записи содержится соответственно 2n1,2n2,...(n1 < n2 < ...)  цифр. Аналогично, пусть  2 2
y1,y2,...  — встретившиеся на доске квадраты из нечетного количества знаков, и в их записи содержится соответственно 2m1 − 1,2m2 − 1,...(m1 < m2 <...)  цифр.

Число  2
xk  содержит 2nk  цифр и не оканчивается на 0,  поэтому  2   2nk−1
xk > 10   ,  откуда       nk−1
xk >10    ,  Число  2
xk+1  получается из    xk  приписыванием некоторого четного количества — обозначим его 2a  — ненулевых цифр. Поэтому   2a2   2      2a 2    2a
10 xk <xk+1 < 10 xk+ 10 .  Из левого неравенства получаем   a
10 xk+ 1≤ xk+1,  следовательно,  2a 2     a        2     2a 2   2a
10 xk+ 2⋅10 xk+ 1≤ xk+1 < 10  xk+10  ,  откуда     a        2a
2⋅10 xk+1 <10  ,  т. е.      a
xk < 10 .  Из этого неравенства следует, что xk  содержит не более a  цифр, т. е. nk ≤a,  тогда из неравенства   a
10 xk+ 1≤xk+1  следует a+ nk ≤nk+1,  откуда 2nk ≤ nk+1.  Аналогичное рассуждение применимо к последовательности     2
yk :yk+1  получается приписыванием к y2k  2a  цифр, yk <10a,  и a ≥mk,  т. е. mk+1 ≥2mk.  Теперь заметим, что в каждой из последовательностей mk  и nk  меньше 50  членов (так как m1,n1 ≥ 1  и m50  и n50  должны быть не меньше, чем 250 > 1000000  ).

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

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!