Разделы 
Дополнительно
Задача по математике - 1620
2019-01-19 
Саша написал на доске ненулевую цифру и приписывает к ней справа по одной ненулевой цифре, пока не выпишет миллион цифр. Докажите, что на доске не более 100 раз был написан точный квадрат.
Решение:
Рассмотрим отдельно числа из нечетного и из четного числа знаков. Пусть $x_{1}^{2},x_{2}^{2},\cdots$ - встретившиеся на доске квадраты из четного количества знаков, и в их записи содержится соответственно $2n_1, 2n_2,\cdots$ ($n_1 < n_2 < \cdots)$ цифр. Аналогично, пусть $y_{1}^{2},y_{2}^{2},\cdots$ - встретившиеся на доске квадраты из нечетного количества знаков, и в их записи содержится соответственно $2m_1 - 1, 2m_2 - 1, \cdots$ $(m_1 < m_2 < \cdots )$ цифр.
Число $x_{k}^{2}$ содержит $n_k$ цифр и не оканчивается на 0, поэтому $x_{k}^{2} > 10^{2n_k-1}$, откуда $x_k > 10^{n_k-1}$. Число $x_{k+1}^2$ получается из $x_k$ приписыванием некоторого четного количества - обозначим его $2a$ - ненулевых цифр. Поэтому $10^{2a}{x_k}^2 < {x_{k+1}}^2 < 10^{2a}{x_k}^2 + 10^{2a}$. Из левого неравенства получаем $10^ax_k + 1 \leq x_{k+1}$, следовательно, $10^{2a}x_k^2 + 2 \cdot 10^ax_k + 1 \leq x_{k+1}^2 < 10^{2a}x_k^2 + 10^{2a}$, откуда $2 \cdot 10^ax_k + 1 < 10^{2a}$, т. е. $x_k < 10^a$. Из этого неравенства следует, что $x_k$ содержит не более $а$ цифр, т. е. $n_k \leq а$, тогда из неравенства $10^ax_k + 1 \leq x_{k+1}$ следует $а + n_k \leq n_{k+1}$, откуда $2n_k \leq n_{k+1}$.
Аналогичное рассуждение применимо к последовательности $\{ y_k \}: y_{k+1}^2$ получается приписыванием к $y_k^22a$ цифр, $y_k < 10^a$, и $а \geq m_k$, т. е. $m_{k+1} \geq 2m_k$. Теперь заметим, что в каждой из последовательностей $m_k$ и $n_k$ меньше 50 членов (так как $m_1, n_1 \geq 1$ и $m_{50}$ и $n_{50}$ должны быть не меньше, чем $2^{50} > 1000000$).
Итак, всего квадратов на доске окажется не более 100.
Саша написал на доске ненулевую цифру и приписывает к ней справа по одной ненулевой цифре, пока не выпишет миллион цифр. Докажите, что на доске не более 100 раз был написан точный квадрат.
Решение:
Рассмотрим отдельно числа из нечетного и из четного числа знаков. Пусть $x_{1}^{2},x_{2}^{2},\cdots$ - встретившиеся на доске квадраты из четного количества знаков, и в их записи содержится соответственно $2n_1, 2n_2,\cdots$ ($n_1 < n_2 < \cdots)$ цифр. Аналогично, пусть $y_{1}^{2},y_{2}^{2},\cdots$ - встретившиеся на доске квадраты из нечетного количества знаков, и в их записи содержится соответственно $2m_1 - 1, 2m_2 - 1, \cdots$ $(m_1 < m_2 < \cdots )$ цифр.
Число $x_{k}^{2}$ содержит $n_k$ цифр и не оканчивается на 0, поэтому $x_{k}^{2} > 10^{2n_k-1}$, откуда $x_k > 10^{n_k-1}$. Число $x_{k+1}^2$ получается из $x_k$ приписыванием некоторого четного количества - обозначим его $2a$ - ненулевых цифр. Поэтому $10^{2a}{x_k}^2 < {x_{k+1}}^2 < 10^{2a}{x_k}^2 + 10^{2a}$. Из левого неравенства получаем $10^ax_k + 1 \leq x_{k+1}$, следовательно, $10^{2a}x_k^2 + 2 \cdot 10^ax_k + 1 \leq x_{k+1}^2 < 10^{2a}x_k^2 + 10^{2a}$, откуда $2 \cdot 10^ax_k + 1 < 10^{2a}$, т. е. $x_k < 10^a$. Из этого неравенства следует, что $x_k$ содержит не более $а$ цифр, т. е. $n_k \leq а$, тогда из неравенства $10^ax_k + 1 \leq x_{k+1}$ следует $а + n_k \leq n_{k+1}$, откуда $2n_k \leq n_{k+1}$.
Аналогичное рассуждение применимо к последовательности $\{ y_k \}: y_{k+1}^2$ получается приписыванием к $y_k^22a$ цифр, $y_k < 10^a$, и $а \geq m_k$, т. е. $m_{k+1} \geq 2m_k$. Теперь заметим, что в каждой из последовательностей $m_k$ и $n_k$ меньше 50 членов (так как $m_1, n_1 \geq 1$ и $m_{50}$ и $n_{50}$ должны быть не меньше, чем $2^{50} > 1000000$).
Итак, всего квадратов на доске окажется не более 100.
