Разделы 
Дополнительно
Задача по математике - 3056
2019-05-06 
Доказать, что существует такая степень числа 2, последние 1000 цифр которой все будут единицами и двойками.
Решение:
Докажем даже более общее предложение, а именно, что каково бы ни было целое число $N$, всегда найдется такая степень числа 2, последние $N$ цифр которой все будут единицами и двойками. Так как $2^5 = 32$ и $2^9 = 512$, то при $N = 1$ и $N = 2$ это утверждение справедливо. Далее доказательство мы проведем при помощи метода математической индукции. Предположим, что последние $N$ цифр числа $2^n$ являются единицами и двойками, и докажем, что в таком случае найдется степень числа 2, последние $N + 1$ цифр которой являются единицами и двойками. Согласно сделанному предположению $2^n = 10^N а + b$, где $b$ есть $N$-значное число, записываемое с помощью двух цифр: 1 и 2. Обозначим число $5^N - 5^{N-1} = 4 \cdot 5^{N-1}$ буквой $r$; тогда согласно теореме Эйлера (задача 3053) разность $2^r - 1$ будет делиться на $5^N$. Отсюда вытекает, что если целое число $k$ делится на $2^{N+1}$, то разность $2^rk - k = k(2^r - 1)$ будет делиться на $2 \cdot 10^N$, т. е. $N$ последних цифр чисел $2^rk$ и $k$ будут совпадать, a $(N + 1)$-е с конца цифры этих чисел будут одинаковой четности.
Рассмотрим теперь следующие пять степеней числа 2:
$2^n, 2^{n+r} = 2^r \cdot 2^n, 2^{n+2r} = 2^r \cdot 2^{n+r}, 2^{n+3r} = 2^r \cdot 2^{n+2r}, 2^{n+4r} = 2^r \cdot 2^{n+3r}$.
Согласно доказанному последние $N$ цифр всех этих чисел совпадают между собой (т. е. все они оканчиваются тем же числом $b$, составленным из двоек и единиц, что и число $2^n$), a $(N+l)$-e с конца цифры у всех у них одновременно четны или нечетны. Докажем теперь, что ни у каких двух из этих пяти чисел $(N + 1)$-е с конца цифры не могут быть одинаковыми Действительно, разность любых двух из наших чисел представима в виде $2^{n+m_1r} (2^{m_2r} - 1)$ где $m_1 = 0, 1,2$ или 3, a $m_2 = 1, 2, 3$ или 4. Если бы эта разность делилась на $10^{N+1}$, то число $2^{m_2r} - 1$ должно было бы делиться на $5^{N+1}$; но так как
$m_2r = m_2 \cdot (5^N - 5^{N-1}) < 5 \cdot (5^N - 5^{N-1}) = 5^{N+1} - 5^N$,
то это противоречит результату задачи 3054.
Итак, $(N+1)$-e с конца цифры выписанных пяти чисел - это или 1, 3, 5, 7 и 9 (в каком-то неизвестном нам порядке) или же 0, 2, 4, 6 и 8. В обоих случаях хотя бы для одного из этих чисел $(N + 1)$-я с конца цифра равна 1 или 2. Значит, во всех случаях существует степень числа 2, последние $N + 1$ цифр которой все являются единицами и двойками; в силу принципа математической индукции отсюда следует требуемое предложение.
Доказать, что существует такая степень числа 2, последние 1000 цифр которой все будут единицами и двойками.
Решение:
Докажем даже более общее предложение, а именно, что каково бы ни было целое число $N$, всегда найдется такая степень числа 2, последние $N$ цифр которой все будут единицами и двойками. Так как $2^5 = 32$ и $2^9 = 512$, то при $N = 1$ и $N = 2$ это утверждение справедливо. Далее доказательство мы проведем при помощи метода математической индукции. Предположим, что последние $N$ цифр числа $2^n$ являются единицами и двойками, и докажем, что в таком случае найдется степень числа 2, последние $N + 1$ цифр которой являются единицами и двойками. Согласно сделанному предположению $2^n = 10^N а + b$, где $b$ есть $N$-значное число, записываемое с помощью двух цифр: 1 и 2. Обозначим число $5^N - 5^{N-1} = 4 \cdot 5^{N-1}$ буквой $r$; тогда согласно теореме Эйлера (задача 3053) разность $2^r - 1$ будет делиться на $5^N$. Отсюда вытекает, что если целое число $k$ делится на $2^{N+1}$, то разность $2^rk - k = k(2^r - 1)$ будет делиться на $2 \cdot 10^N$, т. е. $N$ последних цифр чисел $2^rk$ и $k$ будут совпадать, a $(N + 1)$-е с конца цифры этих чисел будут одинаковой четности.
Рассмотрим теперь следующие пять степеней числа 2:
$2^n, 2^{n+r} = 2^r \cdot 2^n, 2^{n+2r} = 2^r \cdot 2^{n+r}, 2^{n+3r} = 2^r \cdot 2^{n+2r}, 2^{n+4r} = 2^r \cdot 2^{n+3r}$.
Согласно доказанному последние $N$ цифр всех этих чисел совпадают между собой (т. е. все они оканчиваются тем же числом $b$, составленным из двоек и единиц, что и число $2^n$), a $(N+l)$-e с конца цифры у всех у них одновременно четны или нечетны. Докажем теперь, что ни у каких двух из этих пяти чисел $(N + 1)$-е с конца цифры не могут быть одинаковыми Действительно, разность любых двух из наших чисел представима в виде $2^{n+m_1r} (2^{m_2r} - 1)$ где $m_1 = 0, 1,2$ или 3, a $m_2 = 1, 2, 3$ или 4. Если бы эта разность делилась на $10^{N+1}$, то число $2^{m_2r} - 1$ должно было бы делиться на $5^{N+1}$; но так как
$m_2r = m_2 \cdot (5^N - 5^{N-1}) < 5 \cdot (5^N - 5^{N-1}) = 5^{N+1} - 5^N$,
то это противоречит результату задачи 3054.
Итак, $(N+1)$-e с конца цифры выписанных пяти чисел - это или 1, 3, 5, 7 и 9 (в каком-то неизвестном нам порядке) или же 0, 2, 4, 6 и 8. В обоих случаях хотя бы для одного из этих чисел $(N + 1)$-я с конца цифра равна 1 или 2. Значит, во всех случаях существует степень числа 2, последние $N + 1$ цифр которой все являются единицами и двойками; в силу принципа математической индукции отсюда следует требуемое предложение.
