На каждом этаже у дежурной по определению должно быть бесконечное, счетное количество номеров. В противном случае вариантов в смысле номеров комнат у неё будет конечное количество, то есть, каждое двоичное число будет иметь вполне определенное число знаков. Например, 10165 нулей и единиц. В этом случае задача имеет однозначное решение при бесконечном количестве гостиниц и этажей, поскольку любая счетная (потенциальная) бесконечность перекрывает любое конечное число вариантов.
Но, с другой стороны, если на этаже счетное, то есть, бесконечное количество номеров, то и в этом случае будет получен список вариантов, содержащий все возможные комбинации из бесконечного (счетного) числа нулей и единиц. То есть, и в этом случае задача решается однозначно, то есть, список вариантов будет единственным и полным.
" Могу ручаться, что список неполон. Я берусь указать вариант, который наверняка пропущен" [3, с.70-71].
Вполне ожидаема подмена понятий, но её следует показать непосредственно, явно.
"Мы заключили пари. Чтобы выиграть его, я предложил прибить каждый вариант на дверь того номера, которому он соответствовал" [там же].
Сразу же возразим. Напомним читателю, что вариантов составлено столько, сколько номеров на этаже, а не в гостинице целиком. Список отсортирован по возрастанию, но это не имеет принципиального значения, поэтому просто отбросим варианты других этажей, поскольку и одного этажа окажется вполне достаточно.
"А потом я поступил очень просто. Подойдя к двери первого номера, я увидел, что соответствующий вариант начинается с цифры 0. Немедленно в блокноте появилась цифра 1; это и была первая цифра варианта, который мне хотелось составить" [там же].
Здесь заметна некоторая неопределенность. Гостиниц бесконечное число (счетное). Можно также предположить, что, соответственно, этажей и комнат на каждом этаже также счетное (потенциально бесконечное) множество. В этом случае смысл первого номера становится неясен. Нумерация ведётся сквозная? Или в каждой гостинице есть свой первый номер? С этажами тоже не совсем ясно, хотя и проще, поскольку по принятой практике первая цифра номера комнаты равна номеру этажа. И вновь примем решение в пользу рассказчика: отбросим все номера кроме номеров на единственном этаже единственной гостиницы, а в номере комнаты отбросим цифры этажа. Следовательно, на каждом этаже каждой гостиницы будет комната с номером 0, причём под "вариантом", очевидно, подразумевается именно номеркомнаты.
"Когда я подошел к двери второго номера, то первая цифра соответствующего варианта меня не интересовала, ведь первая цифра моего варианта была уже написана. Поэтому все внимание было обращено на вторую цифру. Увидев, что эта цифра 1, я записал в своем блокноте цифру 0. Точно так же, обнаружив, что третья цифра варианта, прибитого к двери третьего номера, тоже 1, я записал в блокноте цифру 0. Вообще, если я обнаруживал, что n-я цифра n-го варианта есть 0, то писал в своем блокноте на n-ом месте цифру 1, если же n-я цифра n-го варианта была 1, то я писал у себя 0. Когда я обошел все номера гостиницы, то в блокноте оказалась записанной последовательность нулей и единиц" [3, с.70-71].
Методика понятна и разумна, но верные ли выводы из неё делает рассказчик?
" Вот, полюбуйтесь на пропущенный вариант.
А откуда известно, что он пропущен?
Он не может быть первым, так как отличается от него первой цифрой, не может быть вторым, так как отличается от него второй цифрой, третьим, так как отличается от него третьей цифрой, и вообще n-м, так как отличается от него n-й цифрой" [там же].
Как видим, метод полностью совпадает с рассмотренным выше, поэтому также ведет к неверному выводу. В его списке номер начинается, например, с цифры 0. Но это всего-навсего первый разряд бинарного числа бесконечной длины. Можно уверенно заявить, что вся монотонная бесконечная последовательность нулей и единиц в точности содержит половину начинающихся с нуля. Например, пятизначное двоичное число:
содержит всего 32 числа, первые 16 из которых начинаются с нуля. Следовательно, если номер первой комнаты начинается с нуля, то номер второй комнаты тоже будет начинаться с нуля. И так на бесконечном количестве дверей. Поэтому в блокноте вторая цифра, как и первая, так же будет единицей. И третья. И четвертая. И так до бесконечности. Счетной.
Но как же так?! Получается, что все комнаты будут иметь один и тот же нулевой номер?! Нет, разумеется. Просто длина последовательности нулей и единиц такова, что прочитать последнюю цифру рассказчику не удастся никогда. Вернее, за бесконечное (счетное) количество времени.
" стало ясно, что какое бы счетное множество вариантов ни взять, всегда найдется вариант, не вошедший в это множество А это и значит, что множество всех вариантов заполнения гостиницы несчетно" [3, с.70-71].
Как видим, вывод о несчетности вариантов явно ошибочен. Похоже, что этого не заметили и программисты или математики в тресте космических гостиниц, которые обязаны были предостеречь руководство от такого тривиального, бессмысленного задания. Бесконечное (счетное) число вариантов бинарных чисел даёт весь натуральный бинарный ряд чисел. Без пропусков и повторов. Каждый дежурный по этажу должен был составить список всех вариантов (то есть, номеров комнат) из бесконечной последовательности бинарных чисел. Неважно, что дежурных много, а гостиниц вообще бесконечное (счетное) количество. Каждый из дежурных предоставит в точности один и тот же список вариантов (номеров).
По поводу "отсутствующего" номера комнаты добавим этот номер в списке есть, но находится среди номеров второй половины бесконечного их количества. Заметим, что при таком способе "нахождения" не проходит и хитрость с отбрасыванием ведущих нулей, то есть:
поскольку в этом случае у второй комнаты в номере отсутствует вторая цифра, у третьей третья, у четвертой четвертая и так далее.
Разрядность и количество чисел в массиве
Легко показать, что причина ошибки заключается в том, что при поиске отсутствующего числа по непонятной причине количество разрядов чисел (записей в блокноте) приравнивалось общему количеству всех чисел. В сущности, это очевидное и даже тривиальное некорректное допущение, и почему оно оказалось незамеченным, непонятно. Действительно, общее количество чисел, их основание и разрядность связаны простым соотношением
где
k количество чисел разрядности n и основанием m;
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 раз больше. И это, якобы пропущенное число, в этой таблице точно есть. Находится оно в третьей строке в седьмой колонке. Заметим, что порядок просмотра номеров в таблице значения не имеет, просто будут получены разные "пропущенные" номера.