Задача из журнала «Квант» (1995, выпуск №4)
- Сколько единиц среди первых 1000 членов этой последовательности?
- Докажите, что в последовательности
$$ c_{1}=2, \quad c_{2}=4, \quad c_{3}=8, \quad c_{4}=1, \quad c_{5}=3, \quad… $$
встретится ровно 57 различных «слов» [latex]c_{k}c_{k+1}…c_{k+12}[/latex] длины 13.
Решение
-
Отметим на «логарифмической шкале» [latex]y=\log_{10}{x} [/latex] числа [latex]x=2^{n}[/latex] (каждая следующая отметка получается из предыдущей сдвигом на расстояние [latex]\log_{10}{2}[/latex]). Число [latex]x[/latex] начинается с [latex]1[/latex], если [latex]10^{k} \le x < 2 \cdot 10^{k+1}[/latex] для некоторого [latex]k[/latex]; соответствующие интервалы на рисунке 1 выделены красным (поскольку длина интервала как раз равна [latex]\log_{10}{2}[/latex], на каждый из них попадает ровно одна отметка). Поскольку
$$ \log_{10}{2} = 0.30103…, \quad 10^{301} \le 2^{1000} < 10^{302}, $$так что [latex]2^{n}(n=0,1,2,…,1000)[/latex] ровно 301 раз перейдет через степень [latex]10[/latex] и поэтому (не считая [latex]2^{0}=1[/latex]) 301-ый её член начинается с 1.
-
Чтобы более детально разобраться в закономерностях последовательности [latex]c_{n}[/latex], свернем логарифмическую шкалу [latex]y=\log{10}{x} [/latex] в «логарифмический круг» [latex]z=y-\left[ y \right][/latex]: каждый отрезок от [latex]10^k[/latex] до [latex]10^{k+1}[/latex] даёт новый оборот круга, а точки [latex]0=\log_{10}{1}, \quad \log_{10}{2}, \quad \log_{10}{3}, \quad …, \quad \log_{10}{9}[/latex] — границы интервалов, в которых расположены значения z, соответствующие различным первым значащим цифрам числа [latex]x[/latex] от [latex]1[/latex] до [latex]9[/latex] (см. рисунок 2).
Прежде чем решать задачу [latex](2)[/latex], объясним идею рассуждения на более простом примере: выясним, сколько разных пар [latex]\left( c_{k}, c_{k+1} \right)[/latex] цифр встречается в нашей последовательности.
(Конечно, ответ — [latex]13[/latex] — можно получить и простым перебором.) Мы должны выяснить, во сколько разных пар из [latex]9[/latex] интервалов [latex]1,…,9[/latex] попадают пары точек [latex]z,z+\log_{10}{2}[/latex] окружности (конечно, здесь сумма берется «по модулю 1», т.е. [latex]z+\log_{10}{2}[/latex] — точка, получающаяся из [latex]z[/latex] «поворотом» на [latex]\log_{10}{2}[/latex]). Для этого достаточно к [latex]9[/latex] точкам деления [latex]0,\quad \log_{10}{2}, \quad \log_{10}{3}, \quad …, \quad \log_{10}{9}[/latex] на окружности добавить еще те, при прибавлении к которым [latex]\log_{10}{2}[/latex] получается одна из этих [latex]9[/latex] точек деления (новые точки деления на рисунке показаны красным). Тогда окружность разобьётся на более мелкие интервалы [latex]\Delta[/latex] так, что для всех [latex]z[/latex] из каждого [latex]\Delta[/latex] пара [latex]z, z+\log_{10}{2}[/latex] попадает в одну и ту же пару интервалов [latex]1,…,9[/latex], а [latex]z[/latex] из разных [latex]\Delta[/latex] дают разные пары цифр.
Точно так же можно разобраться со «словами» любой длины.
Пусть
$$ R: z \rightarrow z+\log_{10}{2}\left(\text{mod 1}\right) $$— поворот окружности, соответствующий уможению на [latex]2: x \rightarrow 2x; \quad L=R^{-1}[/latex] — обратное к [latex]R[/latex] преобразование [latex]z \rightarrow z-\log_{10}{2} \left(\text{mod 1}\right)[/latex]. Чтобы проследить, в какие именно интервалы могут попадать последовательности точек длины 13
$$ z, \quad Rz, \quad …,\quad R^{12}z $$— т.е. какие возможны последовательности цифр
$$ c_{k}c_{k+1}…c_{k+12} $$— достаточно выяснить, на сколько интервалов будет разбит круг точками
$$ \log_{10}{k}, \quad L\left(\log_{10}{k}\right), \quad …, \quad L^{12} \left(\log_{10}{k}\right),$$где [latex]k=1,2,…,9[/latex]. Для точек [latex]z[/latex] из каждого интервала [latex]\Delta[/latex] между этими точками получится своя последовательность «номеров». Заметим, что поскольку
$$ L\left(\log_{10}{2}\right)=0, \quad L\left(\log_{10}{4}\right)=\log_{10}{2}, \quad L\left(\log_{10}{6}\right)=\log_{10}{3}\\L\left(\log_{10}{8}\right)=\log_{10}{4}, \quad L\left(\log_{10}{1}\right)=\log_{10}{5} $$(ведь [latex]\log_{10}{1}[/latex] на окружности совпадает с [latex]\log_{10}{10}[/latex]), то среди точек [latex]L\left(\log_{10}{k}\right)[/latex] появляются лишь четыре новых
$$ L\left(\log_{10}{3}\right)=\log_{10}{\frac{3}{2}}, \quad L\left(\log_{10}{5}\right)=\log_{10}{\frac{5}{2}},\\ L\left(\log_{10}{7}\right)=\log_{10}{\frac{7}{2}},\quad L\left(\log_{10}{9}\right)=\log_{10}{\frac{9}{2}}, $$отмеченных на рисунке красным цветом; точно так же, среди точек [latex]L^{n+1}\left(\log_{10}{k}\right)[/latex] по сравнению с [latex]L^{j}\left(\log_{10}{3}\right)\left(j=0,1,…,n\right)[/latex] появляется лишь четыре новых, соответствующих [latex]k=3,5,7,9.[/latex] Таким образом, среди точек
$$ L^{i}\left(\log_{10}{k}\right),\quad 0 \le i < n, \quad 1 \le k \le 9 $$будет всего [latex]4n+5[/latex] различных (при [latex]n=1[/latex] их число равно [latex]9[/latex], при [latex]n=2[/latex] — [latex]13[/latex]). В частности, при [latex]n=13[/latex] получим ответ: [latex]4 \cdot 13+5=57.[/latex]
Осталось заметить, что последовательность точек [latex]z_{n}[/latex], соответствующих числам [latex]2^{n}[/latex] будет «всюду плотной на окружности» — это следует из иррациональности [latex]\log_{10}{2}[/latex] (если бы некоторый интервал [latex]\delta[/latex] был свободен от точек [latex]z_{n}[/latex] — мы могли бы выбрать его максимальным влево и вправо, — то интервалы [latex]\delta, R \delta, R^{2} \delta, …[/latex] не могли бы пересекаться). Значит, в каждом интервале [latex]\Delta[/latex] будет хоть одна точка [latex]z_{n}[/latex].
Ответ:
- 301.
- Число различных «слов» длины [latex]n[/latex] задается формулой [latex] 4n+5 [/latex]. В частности, при [latex]n=13[/latex] получим ответ: [latex]4 \cdot 13+5=57.[/latex]
А подключить к странице «Кванта» сил уже не хватило…
Возможно, забыл сохранить изменения при редактировании страницы «Кванта». Сейчас должно отображаться корректно.