Олимпиадная задача: количество различных слов длины 13 в последовательности 2ⁿ

  Первая цифра числа 2ⁿ определяется числом  a_n = {n lg 2},  а именно: если  a_n ∈ [0, lg 2),  то первая цифра числа 2ⁿ равна 1, если  a_n ∈ [lg 2, lg 3),  то она равна 2, ..., если  a_n ∈ [lg 9, 1)  – то 9.

  Итак, последовательность первых цифр степеней двойки длины 13 определяется взаимным расположением чисел a_n, ..., a_n+12 и 0,  lg2,  ...,  lg 9.

  Пусть α изменяется от 0 до 1  (α ∈ [0, 1) ).  Рассмотрим числа  α,  {α + lg 2},  {α + 2 lg 2},  ...,  {α + 12 lg 2}.   (*)

  Расположение этих тринадцати чисел среди 0,  lg 2,  lg 3,  ...,  lg 9   ()   определяет последовательность первых цифр чисел N, 2N, 2², ..., 2¹²N,   ()   где  {lg N} = α.  При  α = 0  мы получаем одну из возможных последовательностей первых цифр чисел (). Увеличивая α, мы придём к другой последовательности () тогда, когда хотя бы одно из чисел () совпадёт с каким-то из чисел (**).

  Вычислим количество таких моментов совпадений. Для этого сначала подсчитаем число совпадений (в один момент могут произойти несколько совпадений). Поскольку каждое из чисел () при некотором α совпадёт с каждым из чисел (**), количество совпадений равно  13 · 9 = 117.  Это может происходить одновременно лишь при совпадении каких-то чисел () с числами (**), дробные части которых отличаются на  lg 2:  это пары 0 и  lg 2,  lg 2  и  lg 4,  lg 3  и  lg 6,  lg 4  и  lg 8,  lg 5  и 0. Всякий раз, когда  {α + i lg 2},  1 ≤ i ≤ 12  совпадает со вторым числом одной из этих пар, это совпадение учитывать не нужно, так как он учтён при совпадении  {α + (i – 1) lg 2}  с первым числом той же пары. Следовательно, число моментов совпадений равно 117 – 12·5 = 57.

  Поскольку степень двойки может начинаться с любой заданной комбинации цифр (см. задачу 177898), то для степеней двойки реализуются все 57 найденных вариантов.

Ответ задачи отсутствует