Задача М373‍‍

Решение этой задачи требует только аккуратных логических умозаключений для бесконечных множеств. Вот самый характерный пример: «Пусть $P$‍‍ — какое‑то свойство члена последовательности $x_n$‍.‍ Тогда либо для всех членов, начиная с некоторого, свойство $P(x_n)$‍‍ выполнено, либо найдётся бесконечно много членов, для которых $P(x_n)$‍‍ не выполнено». Рассуждения такого типа особенно часто встречаются в учебниках по анализу — при изучении пределов и т. п.

а) Конечные куски последовательности цифр (натуральные числа) будем называть словами (для нас это действительно слова — в алфавите из «букв» 0, 1, $\ldots$‍,‍ 9). Тогда либо для каждого знака нашей десятичной дроби (начиная с некоторого) есть слово первого класса, начинающееся с этого знака, либо существует бесконечно много знаков таких, что все начинающиеся с них слова — не первого класса (т. е. все — второго класса).

Первый случай: мы можем (начиная с некоторого места) отрезать от нашей дроби последовательно одно слово первого класса за другим, т. е. десятичную дробь удастся разрезать на слова первого класса (кроме, быть может, начального слова; рис. 7).

Второй случай: отметим (на рисунке 7 — красным) знаки нашей дроби, с которых начинаются слова лишь второго класса. Ясно, что слова, начинающиеся красными буквами и идущие до следующей красной буквы, дают требуемое разрезание дроби на слова второго класса.

б) Пусть слова разбиты на $N$‍‍ классов. Мы докажем индукцией по $N$‍‍ утверждение задачи в несколько усиленном виде (как часто бывает, доказать большеоказывается легче‍). А именно, мы докажем, что если дробь уже как‑то (начиная с некоторого места $n_0$‍)‍ разделена на куски — назовём их слогами, — то можно её разрезать (начиная с некоторого места $n_1$‍)‍ на слова одного класса, не разрезая слогов, т. е. так, что каждое слово будет состоять из нескольких слогов. Вы легко проверите, что для $N=2$‍‍ этот усиленный вариант доказывается точно так же, как прежний (роль «знаков» дроби играют не цифры, а слоги). Но формально это и не нужно: ведь начать индукцию можно с $N=1$‍,‍ где всё очевидно. Под словом мы понимаем ниже «слово из слогов».

Шаг индукции. Пусть для $N-1$‍‍ классов утверждение доказано, а у нас их $N$‍.‍ Пусть наша дробь разрезана на слоги (рис. 8). Тогда либо для каждого слога в дроби (начиная с некоторого) найдётся слово первого класса, начинающееся с этого слога, либо существует бесконечно много слогов таких, что все начинающиеся с них слова — не первого класса. Первый случай ясен. Во втором случае разрежем всю дробь на куски, начинающиеся с «красных» слогов, и объявим эти более крупные куски слогами. Поскольку все слова, состоящие из таких укрупнённых слогов, не первого класса, у нас теперь могут быть слова не более чем $N-1$‍‍ разных классов; и по предположению индукции мы можем разрезать нашу дробь требуемым образом.

Приведённое здесь доказательство существования требуемого разрезания неконструктивно — не даётся никакого общего способа построить (сконструировать) разрезание для произвольных правил, задающих последовательность, и разбиения слов на классы.