m – основание чисел: десятичные, двоичные и т.д.;
n – разрядность чисел, числового ряда.
Например, общее количество чисел с основанием 10 (десятичные) и разрядностью 5 равно 100 000, то есть, от 00000 до 99 999. А количество чисел с основанием 2 (бинарных) и числом разрядов 16, соответственно, равно 216 – или 65 536 чисел от 0000 0000 0000 0000 до 1111 1111 1111 1111. Точно такие же соотношения можно составить и для любых других оснований – шестнадцатеричного, восьмеричного и так далее.
Рассмотрим массив бинарных чисел, использованных в "блокнотном методе", и возможность метода определить число, номер, не использованный при нумерации комнат. Сначала вновь обратимся к примеру с массивом пятизначных чисел, теперь уже двоичных, бинарных.
Обобщённо в двоичном коде пятизначное число можно записать как nnnnn c диапазоном от 00000 до 11111. Количество этих чисел равно 25 = 32. Поскольку их относительно мало, можем записать все их в виде таблицы 4х8 – слева направо, сверху вниз:
Теперь можно воспользоваться "блокнотным методом". Рассказчик и его герой в рассказе, а также все их последователи искали пропущенное число поразрядно, то есть, переходя от двери к двери комнат отеля, добавляли к записи в блокноте всё новый и новый разряд, полагая, что тем самым они просмотрели все возможные числа, номера комнат. Но на самом деле, как видно из соотношения, они переберут только количество чисел, равное их разрядности.
Мы, согласно традиции метода, предполагаем, что кому-то удалось пересчитать и перенумеровать все 32 числа в этой таблице. Попробуем доказать, что счётчик всё-таки пропустил, по меньшей мере, одно число. Итак, смотрим на первое число. Его первый разряд равен нулю, поэтому записываем в блокнот единицу: 1nnnn. Остальные четыре цифры нам пока неизвестны. Теперь смотрим на второе число, двигаясь по таблице сверху вниз. Видим, что вторая цифра второго числа равна единице, поэтому записываем в блокнот цифру 0 вторым разрядом нашего числа: 10nnn. Смотрим третье число и видим, что третья цифра равна нулю. Делаем запись в блокнот: 101nn. Таким же образом записываем и четвёртую цифру 1 в блокнот, заметив, что четвёртая цифра четвёртого числа в таблице равна нулю: 1011n. Последнее, пятое число в таблице берём рядом с предыдущим: последнее число в следующей колонке. В результате получаем в блокноте окончательно число 10110. Согласно "блокнотному правилу" наше число отличается от первого первой цифрой, от второго – второй, от третьего – третьей и так далее. Следовательно, мы должны сделать вывод, что счётчик не пронумеровал это число в процессе подсчёта, ведь оно отличается первым разрядом от первого числа… и так далее. Однако… это явно не так. Реально мы просмотрели только 5 (пять) чисел в колонках, хотя общее количество чисел равно 32 – в 6 раз больше. И это, якобы пропущенное число, в этой таблице точно есть. Находится оно в третьей строке в седьмой колонке. Заметим, что порядок просмотра номеров в таблице значения не имеет, просто будут получены разные "пропущенные" номера.
Еще раз отметим, что метод просматривает совсем даже не все числа, а только их количество, равное разрядности числа. Но ведь по условиям рассказа об отелях номеров на этаже – бесконечное количество, то есть, разрядность каждого числа также равна бесконечности. Тем не менее, это ровным счетом ничего не меняет, в этом случае герой рассказа точно так же просмотрит не все числа, а только их часть, и найденное им якобы отсутствующее число обязательно будет присутствовать среди чисел, до которых он просто никогда не дойдёт.
Как говорится, что-то пошло не так. А не так пошло использованное "блокнотное правило". Мы в рассматриваемом общем массиве чисел можем, имеем право просмотреть только 5 (пять!) чисел. Любое следующее число обязало бы нас приписать к "найденному" числу ещё один разряд, но в нашем массиве нет 6-разрядных чисел. Отношение разрядности чисел к их количеству (7) в массиве описывается простым уравнением:
Здесь n – это основание массива: в нашем случае бинарных чисел m = 2. Для десятичных чисел основание m = 10, для шестнадцатиразрядных hex-чисел m = 16. Соответственно, n – это разрядность чисел, в нашем случае n = 5, следовательно, N ~ 1/6. Используя это уравнение, мы можем определить соотношение N и для других, например, для 10-разрядных бинарных чисел:
Замечаем, что при увеличении разрядности чисел отношение уменьшается. В пределе, какой рассматривается в задаче об отеле Гильберта, разрядность чисел – номеров комнат в отелях стремится к бесконечности.