Разделы 
Дополнительно
Задача по математике - 3257
2019-05-29 
Рассмотрим степени пятерки:
$1, 5, 25, 125, 625, \cdots$.
Образуем последовательность их первых цифр:
$1, 5, 2, 1, 6, \cdots$.
Докажите, что любой кусок этой последовательности, записанный в обратном порядке, встретится в последовательности первых цифр степеней двойки ($1, 2, 4, 8, 1, 3, 6, 1, \cdots$).
Решение:
Достаточно доказать, что любой начальный кусок последовательности первых цифр степеней пятерки встречается (в обратном порядке) в последовательности первых цифр степеней двойки.
Рассмотрим числа: $\frac{1}{2}, \frac{1}{4}, \cdots, \frac{1}{2^n}$. Последовательность первых ненулевых цифр их десятичных записей есть в точности последовательность первых цифр десятичных записей чисел $5, 25, \cdots, 5^n$. Таким образом, если добавить отрицательные степени, то утверждение задачи будет выполнено.
Для решения нашей задачи следует «проимитировать» отрицательные степени. Для этого достаточно показать, что для любого k существует такая степень двойки $x = 2^n$, десятичная запись которой имеет вид
$\underbrace{100 \cdots 0}_{k \:нулей} y$ (1),
где $y$ — оставшаяся часть десятичной записи. Иными словами, $x = 10^N + y$, причем $y < 10^{N-k}$.
В этом случае $2^{n-1} = 2^n/2 = 500 \cdots 0*, 2^{n-2} = 250 \cdots 0*, 2^{n-3} = 1250 \cdots 0*$. Точнее,
$2^{n-l} = \frac{x}{2^l} = \frac{10^N + y}{2^l} = 10^{N-l}5^l + \frac{y}{2^l}$,
так что первая цифра числа $2^{n-l}$ совпадает с первой цифрой числа $5^l$ при $l < k$.
Итак, осталось доказать, что для любого $k$ существует степень двойки вида (1).
Первое доказательство. Ясно, что найдутся две степени двойки, у которых первые $k +1$ цифр совпадают (так как наборов из $k + 1$ цифр — конечное число, а степеней двойки — бесконечное). Разделим одну такую степень на другую (большую на меньшую). Докажем следующее утверждение.
Лемма. Пусть $у$ степеней двойки $2^a$ и $2^b (a > b)$ совпадают первые $k +1$ цифр. Тогда если первая цифра, в которой числа $2^a$ и $2^b$ различаются, у числа $2^a$ больше, чем у числа $2^b$, то частное является степенью двойки, которая начинается с единицы и $k$ нулей. Если же первая несовпадающая цифра больше у числа $2b$, то частное начинается с $k$ девяток.
Доказательство. Обозначим число, образованное первыми $k +1$ цифрами чисел $2^a$ и $2^b$ через $D$. Пусть число $2^a$ — $p$-значное, а число $2^b$ — $q$-значное ($p \geq q$). Тогда $2^a = 10^{p-k-1} D + \alpha, 2^b = 10^{q-k-1} D + \beta$, где $\alpha < 10^{p-k-1}, \beta < 10^{q-k-1}$. Имеем
$|2^{a-b} - 10^{p-q}| = \left |\frac {10^{p-k-1} D + \alpha}{10^{p-k-1} D + \beta} - 10^{p-q} \right | = \frac {|\alpha - `10^{p-q} \beta}{10^{q-k-1} D + \beta} < \frac {10^{p-k-1}}{10^{q-1}} = 10^{p-q-k}$. (2)
Если первая несовпадающая цифра больше у числа $2^a$, то $\alpha > 10^{p-q} \beta$, так что последнее заключенное в знаки модуля выражение в формуле (2) положительно. Но тогда и остальные выражения, заключенные в знаки модуля, положительны, и предыдущее неравенство можно переписать в виде
$10^{p-q} < 2^{a-b} < 10^{p-q} + 10^{p-q-k}$,
так что $2^{a-b}$ начинается с 1 и $k$ нулей. Случай, когда первая несовпадающая цифра больше у числа $2^b$, разбирается аналогично. Лемма доказана.
Итак, $2^{a-b}$ начинается либо с 1 и $k$ нулей, либо с $k$ девяток. В первом случае задача решена, во втором случае поступим следующим образом: пусть число $2^{a-b}$ состоит из $N$ цифр. Повторяя операцию, мы можем построить либо степень двойки, начинающуюся с 1 и $N$ нулей (тогда все доказано), либо степень двойки $2^c$, начинающуюся с $N$ девяток. У степеней двойки $2^c$ и $2^{a-b}$ совпадают первые $k$ цифр, а первая цифра, в которой они различаются, больше у числа $2^c$ (так как у числа $2^c$ она равна 9). Согласно лемме число $2^c/2^{a-b}$ начинается с 1 и $k — 1$ нулей. Так как число $k - 1$ может быть сколь угодно большим, задача решена.
Второе доказательство. Существование степени двойки вида (1) можно доказать, используя стандартные теоремы об иррациональных числах.
Достаточно доказать, что для любого $k$ существуют такие $a$ и $b$, что
$0 \leq 2^a — 10^b < 10^{b-k}$.
Это равносильно неравенствам
$1 \leq \frac{2^a}{10^b} < 1 + \frac{1}{10^k}$.
Логарифмируя по основанию 10, получим неравенства
$0 \leq a log_{10} 2 — b < \epsilon$,
где через $\epsilon$ мы обозначили $log_{10} \left ( 1 + \frac{1}{10^k} \right )$. Наконец, можно переписать неравенство в виде $\{a log_{10} 2
\} < \epsilon$ (фигурные скобки обозначают дробную часть числа). Число $log_{10} 2$, очевидно, иррационально (впрочем, если бы оно было рациональным, то в качестве $a$ можно было бы взять его знаменатель), так что наше утверждение следует из общего факта: последовательность $a_n = \{n \alpha \}$ при иррациональном $\alpha$ всюду плотна на отрезке $[0; 1]$.
Рассмотрим степени пятерки:
$1, 5, 25, 125, 625, \cdots$.
Образуем последовательность их первых цифр:
$1, 5, 2, 1, 6, \cdots$.
Докажите, что любой кусок этой последовательности, записанный в обратном порядке, встретится в последовательности первых цифр степеней двойки ($1, 2, 4, 8, 1, 3, 6, 1, \cdots$).
Решение:
Достаточно доказать, что любой начальный кусок последовательности первых цифр степеней пятерки встречается (в обратном порядке) в последовательности первых цифр степеней двойки.
Рассмотрим числа: $\frac{1}{2}, \frac{1}{4}, \cdots, \frac{1}{2^n}$. Последовательность первых ненулевых цифр их десятичных записей есть в точности последовательность первых цифр десятичных записей чисел $5, 25, \cdots, 5^n$. Таким образом, если добавить отрицательные степени, то утверждение задачи будет выполнено.
Для решения нашей задачи следует «проимитировать» отрицательные степени. Для этого достаточно показать, что для любого k существует такая степень двойки $x = 2^n$, десятичная запись которой имеет вид
$\underbrace{100 \cdots 0}_{k \:нулей} y$ (1),
где $y$ — оставшаяся часть десятичной записи. Иными словами, $x = 10^N + y$, причем $y < 10^{N-k}$.
В этом случае $2^{n-1} = 2^n/2 = 500 \cdots 0*, 2^{n-2} = 250 \cdots 0*, 2^{n-3} = 1250 \cdots 0*$. Точнее,
$2^{n-l} = \frac{x}{2^l} = \frac{10^N + y}{2^l} = 10^{N-l}5^l + \frac{y}{2^l}$,
так что первая цифра числа $2^{n-l}$ совпадает с первой цифрой числа $5^l$ при $l < k$.
Итак, осталось доказать, что для любого $k$ существует степень двойки вида (1).
Первое доказательство. Ясно, что найдутся две степени двойки, у которых первые $k +1$ цифр совпадают (так как наборов из $k + 1$ цифр — конечное число, а степеней двойки — бесконечное). Разделим одну такую степень на другую (большую на меньшую). Докажем следующее утверждение.
Лемма. Пусть $у$ степеней двойки $2^a$ и $2^b (a > b)$ совпадают первые $k +1$ цифр. Тогда если первая цифра, в которой числа $2^a$ и $2^b$ различаются, у числа $2^a$ больше, чем у числа $2^b$, то частное является степенью двойки, которая начинается с единицы и $k$ нулей. Если же первая несовпадающая цифра больше у числа $2b$, то частное начинается с $k$ девяток.
Доказательство. Обозначим число, образованное первыми $k +1$ цифрами чисел $2^a$ и $2^b$ через $D$. Пусть число $2^a$ — $p$-значное, а число $2^b$ — $q$-значное ($p \geq q$). Тогда $2^a = 10^{p-k-1} D + \alpha, 2^b = 10^{q-k-1} D + \beta$, где $\alpha < 10^{p-k-1}, \beta < 10^{q-k-1}$. Имеем
$|2^{a-b} - 10^{p-q}| = \left |\frac {10^{p-k-1} D + \alpha}{10^{p-k-1} D + \beta} - 10^{p-q} \right | = \frac {|\alpha - `10^{p-q} \beta}{10^{q-k-1} D + \beta} < \frac {10^{p-k-1}}{10^{q-1}} = 10^{p-q-k}$. (2)
Если первая несовпадающая цифра больше у числа $2^a$, то $\alpha > 10^{p-q} \beta$, так что последнее заключенное в знаки модуля выражение в формуле (2) положительно. Но тогда и остальные выражения, заключенные в знаки модуля, положительны, и предыдущее неравенство можно переписать в виде
$10^{p-q} < 2^{a-b} < 10^{p-q} + 10^{p-q-k}$,
так что $2^{a-b}$ начинается с 1 и $k$ нулей. Случай, когда первая несовпадающая цифра больше у числа $2^b$, разбирается аналогично. Лемма доказана.
Итак, $2^{a-b}$ начинается либо с 1 и $k$ нулей, либо с $k$ девяток. В первом случае задача решена, во втором случае поступим следующим образом: пусть число $2^{a-b}$ состоит из $N$ цифр. Повторяя операцию, мы можем построить либо степень двойки, начинающуюся с 1 и $N$ нулей (тогда все доказано), либо степень двойки $2^c$, начинающуюся с $N$ девяток. У степеней двойки $2^c$ и $2^{a-b}$ совпадают первые $k$ цифр, а первая цифра, в которой они различаются, больше у числа $2^c$ (так как у числа $2^c$ она равна 9). Согласно лемме число $2^c/2^{a-b}$ начинается с 1 и $k — 1$ нулей. Так как число $k - 1$ может быть сколь угодно большим, задача решена.
Второе доказательство. Существование степени двойки вида (1) можно доказать, используя стандартные теоремы об иррациональных числах.
Достаточно доказать, что для любого $k$ существуют такие $a$ и $b$, что
$0 \leq 2^a — 10^b < 10^{b-k}$.
Это равносильно неравенствам
$1 \leq \frac{2^a}{10^b} < 1 + \frac{1}{10^k}$.
Логарифмируя по основанию 10, получим неравенства
$0 \leq a log_{10} 2 — b < \epsilon$,
где через $\epsilon$ мы обозначили $log_{10} \left ( 1 + \frac{1}{10^k} \right )$. Наконец, можно переписать неравенство в виде $\{a log_{10} 2
\} < \epsilon$ (фигурные скобки обозначают дробную часть числа). Число $log_{10} 2$, очевидно, иррационально (впрочем, если бы оно было рациональным, то в качестве $a$ можно было бы взять его знаменатель), так что наше утверждение следует из общего факта: последовательность $a_n = \{n \alpha \}$ при иррациональном $\alpha$ всюду плотна на отрезке $[0; 1]$.
