Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

о подсчёте рациональных чисел

Случайно наткнулся на небольшую милую статью о красивом способе подсчёта рациональных чисел.

Первым "посчитал" рациональные числа Кантор, доказавший во второй половине 19-го века существования разных видов бесконечности. Он доказал, что рациональные числа представляют собой счётное множество (что означает - бесконечное множество, имеющее столько же членов, сколько множество натуральных чисел; иными словами, рациональные числа можно все "пересчитать" с помощью натуральных), а действительные - несчётное множество: их пересчитать с помощью натуральных чисел невозможно.

"Пересчитать" множество с помощью натуральных чисел проще всего, выстроив элементы данного множества в бесконечный ряд, и позаботившись при этом, чтобы каждый элемент в этом ряду на каком-то месте оказался. Например, пересчитать целые числа можно так:

0, 1, -1, 2, -2, 3, -3, 4, -4, ...

В этом списке каждое целое число рано или поздно встретится, и поэтому мы можем каждому целому числу поставить в соответствие натуральное - его номер в этом списке. Это и значит, что множество целых чисел счётное. Но если бы мы пробовали его пересчитать так: 0, 1, 2, 3, .... то это было бы неправильной стратегией, т.к. мы никогда бы не "дошли" до отрицательных чисел.

Стандартный способ пересчёта рациональных чисел вот какой:



(ради простоты здесь и далее будем подсчитывать только положительные рациональные числа; если их можно "пересчитать" натуральными, то 0 и отрицательные к ним можно добавить при помощи того же трюка, который позволяет пересчитать целые числа)

Сначала мы выстраиваем все положительные рациональные числа в бесконечном квадрате: строки и столбцы квадрата перенумерованы натуральными числами, а внутри квадрата в каждой клетке стоит рациональное число, равное частному номера столбца и номера строки. Ясно, что каждое рациональное число находится в этом квадрате. А затем мы его пересчитываем "по диагоналям" (картинка справа), начиная с левого верхнего угла, потом диагональ размером в два числа, потом следующая итд. итд. Ясно, что двигаясь таким образом, мы рано или поздно дойдём до любого числа в квадрате, а значит, в нашем списке будут все положительные рациональные числа.

Этот стандартный способ очень прост, но у него есть эстетические недостатки: например, в этом списке есть повторы: каждое рациональное число повторяется в нём бесконечное число раз (например, 1/2 встречается также как 2/4, 4/8 итд.) Это не мешает доказательству, т.к. эти повторы можно просто выбрасывать, строя список, но тогда для общего его члена не будет красивой лёгкой формулы.

Всё это не слишком важные вопросы, и, тем не менее, красивый другой способ пересчёта рациональных чисел, описанный в прочитанной мной статье, и свободный от этих недостатков, мне очень понравился. Ничего нового он не доказывает, он просто демонстрирует красивую конструкцию, а также, при доказательстве свойств этой конструкции, силу принципа наименьшего элемента, который гласит, что в любом непустом множестве натуральных чисел есть наименьший элемент.

Принцип наименьшего элемента эквивалентен принципу математической индукции по натуральным числам. Их можно легко доказать один с помощью другого. Например, предположим, что какое-то утверждение S выполняется для числа 1, и если оно выполняется для всех k<n, то выполняется также для n; и докажем теперь, что оно выполняется для любого n (принцип индукции). Предположим, что есть такие n, для которых S не выполняется; возьмём множество всех таких n. Согласно принципу наименьшего элемента у этого множества есть наименьший элемент M. Но если M=1, то это противоречит условию, т.к. S выполняется для 1; а если M>1, то S выполняется для всех k<M согласно минимальности M, и тогда S выполняется для M согласно условию. В любом случае получаем противоречие.

Можно доказать и наоборот: с помощью индукции доказать, что любое непустое множество имеет наименьший элемент. Для этого достаточно показать индукцией по n, что если n принадлежит множеству X натуральных чисел, то в X есть наименьший элемент. Если n=1, это очевидно, т.к. 1 и будет наименьший элемент. Если это утверждение верно для всех k<n, то пусть X будет множеством, содержащим число n. Если в X есть какие-то k<n, то утверждение верно по предположению; а если их нет, то n и будет наименьшее число. В любом случае в X есть наименьший элемент.


Итак, вот эта конструкция. Построим бесконечное дерево, в вершинах которого находятся положительые рациональные числа, следующим образом:



Принцип построения дерева вот какой. В корне дерева стоит число 1/1. Далее, у каждой вершины есть двое сыновей. Если в вершине стоит число i/j, то в левом сыне будет стоять число i/i+j, а в правом - число i+j/j:



Теперь, последовательно используя принцип наименьшего элемента, докажем следующие утверждения про наше дерево:
  • В каждой вершине дерева находится число вида i/j, где числитель и знаменатель - положительные натуральные числа. Это очевидно из построения и может быть формально доказано тривиальной индукцией.
  • Для каждой вершины верно, что в левом её сыне находится число меньше единицы, а в правом - число больше единицы. Это очевидно из построения (в левом сыне числитель меньше знаменателя, в правом - наоборот). Отсюда следует, что единица в этом дереве может находится только в корне.
  • В каждой вершине дерева находится несократимая дробь. Предположим, что это не так, тогда есть вершины, в которых расположены сократимые дроби, т.е. такие, для которых у числителя и знаменателя есть общий делитель больше 1. Из всех таких вершин выберем те, у которых наименьший знаменатель (мы здесь используем принцип наименьшего элемента: смотрим на множество знаменателей всех таких вершин и выбираем наименьший элемент); из всех этих вершин выберем вершину с наименьшим числителем. Пусть мы получили вершину, в которой записано число i/k, и у i с k есть общий делитель больше единицы. Не может быть, чтобы i=k, т.к. в любом сыне дерева записано число больше или меньше единицы, а 1 записана только в корне дерева в виде 1/1, и это несократимая дробь. Значит, либо i меньше k, либо наоборот. Если i<k, то у вершины i/k есть "отец" i/k-i. У чисел i и k-i тоже есть общий делитель, тот же, что у i и k, но у числа i/k-i знаменатель меньше, чем у i/k, что противоречит минимальности при выборе знаменателя. Если k<i, то у вершины i/k есть "отец" i-k/k, который тоже сократимая дробь, с тем же знаменателем, что у i/k, но с меньшим числителем - противоречит минимальности при выборе числителя. В любом случае получаем противоречие, поэтому сократимых дробей в дереве нет.
  • В дереве встречается каждое положительное рациональное число. Предположим, что это не так. Тогда есть непустое множество рациональных чисел, которые не встречаются в дереве; выберем из них сначала наименьший знаменатель, а потом среди всех с этим знаменателем наименьший числитель, и пусть это будет число i/k. Если i<k, то у числа i/k-i знаменатель меньше, и поэтому оно находится в дереве; но тогда i/k - его левый "сын". Если i>k, то у числа i-k/k тот же знаменатель, но меньший числитель, и поэтому оно находится в дереве; но тогда i/k - его правый "сын". В любом случае получаем противоречие, поэтому любое положительное рациональное число находится в дереве.
  • Каждое положительное рациональное число находится в дереве всего один раз, без повторов. Предположим, что это не так. Среди всех чисел, находящихся больше одного раза в дереве, выберем какое-нибудь, которое находится (в одном из своих повторов) на наименьшем уровне дерева (т.е. "строке" в картинке выше). Пусть это уровень номер k. k не может быть равно 1, т.к. на первом уровне находится только число 1/1, а оно не повторяется больше нигде (см. выше). Значит, k>1. Наше число, находящееся в вершине A на уровне k, встречается ещё хотя бы один раз в вершине B где-нибудь ещё в дереве (возможно, и на том же уровне). Может ли быть, что вершины A и B - сыновья одной вершины? Нет, т.к. у любой вершины один сын меньше 1, другой больше, и они не могут быть равны. Значит, A и B - сыновья разных вершин; но тогда отец A и отец B тоже равны между собой (сын определяет отца; если сын = i/k для i<k, то отец = i/k-i; если сын = i/k для i>k, то отец = i-k/k), причём отец A находится на уровне k-1, что противоречит минимальности выбора k. Значит, каждое число повторяется в дереве только один раз.

Мы уже доказали, что можно пересчитать все положительные рациональные числа: в дереве встречаются все такие числа по одному разу, так что можно их пересчитать, просто идя по дереву уровень за уровнем, слева направо по каждому уровню. Ясно, что таким образом рано или поздно дойдёшь до любой вершины дерева.

Но оказывается, у этой конструкции есть ещё несколько интересных особенностей. Пусть g(k) - число в k-й вершине в описанном выше обходе дерева слева направо и сверху вниз. При этом начнём с k=0, т.е. самая первая вершина будет "нулевой" (это окажется удобным впоследствии). Тогда
  • Для каждого k верно, что знаменатель g(k) равен числителю g(k+1).

    Доказательство: если g(k) и g(k+1) - два идущих друг за другом сына одного отца, тогда это очевидно из построения дерева (т.к. это числа вида i/i+k и i+k/k). Если g(k) - "правый" сын какого-то отца, а g(k+1) - "левый" сын другого, тогда знаменатель g(k) равен знаменателю его отца, а числитель g(k+1) равен числителю его отца, и их отцы находятся рядом друг с другом на предыдущем уровне, и потому тоже имеют вид g(i) и g(i+1) для какого-то i. Значит, индукция по номеру уровня доказывает утверждение в этом случае. Осталось рассмотреть, что происходит, когда g(k) и g(k+1) находятся на разных уровнях. Но тогда g(k) - число в самой правой вершине своего уровня, и знаменатель g(k) равен 1; а g(k+1) - число в самой левой вершине своего уровня, и его числитель тоже равен 1 (см. картинку).

Обозначим через f(k) числитель k-й вершины при обходе дерева, т.е. числитель g(k). Тогда из вышеописанного следует, что список всех рациональных чисел можно построить с помощью последовательности f(0), f(1), f(2), f(3).... следующим образом: f(0)/f(1), f(1)/f(2), f(2)/f(3), f(3)/f(4)... , деля каждый раз следующее по списку число в последовательности f на следующее за ним.

По-моему, это красиво. Но и это ещё не всё: оказывается, что саму последовательность f(k) можно описать независимым образом, наполнить её "смыслом". А именно: f(k) - количество путей, с помощью которых k можно представить в виде суммы степеней двойки, так что каждую степень можно использовать не более двух раз.

Например, вот несколько первых членов последовательности f(k) (из картинки выше):

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

Значит, скажем, f(9)=3 (помним, что счёт f(k) начинается с k=0). И есть ровно 3 способа записать 9 в виде суммы степеней двойки, используя каждую степень не более двух раз (помня при этом, что 1 - тоже степень двойки, нулевая):

9=8+1
9=4+4+1
9=4+2+2+1

А f(10)=5, и для десятки есть пять способов: 8+2, 8+1+1, 4+4+2, 4+4+1+1, 4+2+2+1+1.

Наконец, докажем строго, что f(k) имеет именно этот смысл. Для этого построим рекурсивное определение f(k) и докажем, что b(k), если обозначить так кол-во способов представить k в виде суммы степеней двойки, не используя каждую более чем дважды, удовлетворяет тому же определению.

Во-первых, f(0)=1, т.к. первая вершина в нашем обходе - 1/1, и её числитель равен 1.
Далее, посмотрим на n-ю вершину в обходе: в ней стоит число f(n)/f(n+1). Пользуясь формулами постройки дерева, видим, что её левый сын равен f(n) / (f(n)+f(n+1)), а правый сын равен (f(n) + f(n+1)) / f(n+1). Но, с другой стороны, её левый сын - это 2n+1-я вершина в том же обходе, а правый сын - 2n+2-я (в этом легко убедиться, посмотрев на картинку, и легко доказать строго: сыновья n-й вершины - 2n+1-я и 2n+2-я вершины в обходе). Значит, f(2n+1) равен числителю левого сына, т.е. f(n), а f(2n+2) равен числителю правого сына, т.е. f(n)+f(n+1). Мы получили следующие рекурсивные формулы:
  • f(0)=1
  • f(2n) = f(n) + f(n+1)
  • f(2n+1) = f(n)
Ясно, что вместе они полностью определяют все значения f. Значит, осталось только доказать, что b(k) выполняет те же формулы.
  • b(0)=1, т.к. есть только один способ представить 0 в виде суммы степеней двойки: "пустая" сумма без единого слагаемого (если этот трюк не убеждает, то можно просто объявить b(0)=1 по определению и проверить, что использование этого значения согласуется с формулами при подсчёте b(1) и b(2), а для всех больших значений аргумента это уже неважно).
  • Пусть теперь наш аргумент - 2k+1, т.е. нечётное число. Тогда в его представлении в виде суммы степеней двойки обязана участовать единица, причём ровно один раз. Если мы теперь уберём эту единицу, а все остальные слагаемые поделим на 2, то получим представление в виде степеней двойки числа k. И наоборот, если есть представление числа k, можно все слагаемые умножить на 2 и прибавить ко всему 1 и получить представление числа 2к+1. Из этого ясно, что кол-во представлений для 2k+1 и k равно, т.е. b(2k+1)=b(k).
  • Пусть теперь наш аргумент - 2k+2, т.е. чётное число. Для любого представления 2k в виде суммы степеней двойки есть два случая: либо в нём не участвует ни одна единица, и тогда, поделив все слагамые на 2, получим представление числа k+1; либо в нём участвуют две единицы, тогда выбросим их и поделим оставшееся на 2, и получим представление числа k. Рассуждая так же, как в прошлом пункте, видим, что b(2k+2) = b(k+1) + b(k).


Всё.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 20 comments