- С меня хватит! — воскликнул директор.- Сначала я в полную гостиницу поместил одного постояльца, потом еще 999 999, потом еще бесконечно много жильцов; а теперь от меня хотят, чтобы в нее вместилось еще бесконечное множество бесконечных множеств жильцов. Нет, гостиница не резиновая, пусть где хотят, там и помещают!
Но приказ есть приказ, и через пять дней надо было все подготовить к встрече новых постояльцев. Эти дни в гостинице никто не работал — все думали, как решить задачу. Был объявлен конкурс с премией — туристическим путешествием по одной из галактик. Но все предлагавшиеся решения отвергались как неудачные. Так, младший повар предложил оставить жильца из первого номера нашей гостиницы в том же № 1, из второго номера переселить в № 1001, из третьего номера — в № 2001 и т. д. После этого поселить жильцов второй гостиницы в № 2, 1002, 2002 и т. д. нашей гостиницы, жильцов третьей гостиницы — в № 3, 1003, 2003 и т. д. Проект был отвергнут, так как уже жители первых 1000 гостиниц займут все номера и некуда будет поселить жителей 1001-й гостиницы.
Мне вспомнилось по этому поводу, что, когда раболепные римские сенаторы предложили императору Тиберию переименовать в его честь месяц сентябрь в "тиберий" (предыдущие месяцы уже получили имена императоров Юлия и Августа), он язвительно спросил их: "А что же вы предложите тринадцатому цезарю?"
Неплохой вариант предложил бухгалтер гостиницы. Он посоветовал воспользоваться свойствами геометрической прогрессии и расселить постояльцев так: жителей первой гостиницы — в № 2, 4, 8, 16, 32 и т. д. (эти числа образуют геометрическую прогрессию со знаменателем 2). Жителей второй гостиницы — в № 3, 9, 27, 81 и т. д. (а эти числа образуют геометрическую прогрессию со знаменателем 3). Так же предложил он расселять и жителей остальных гостиниц. Но директор спросил его:
- А для третьей гостиницы надо использовать прогрессию со знаменателем 4?
- Конечно,- ответил бухгалтер.
- Тогда ничего не получится, ведь в четвертом номере уже живет обитатель первой гостиницы, а теперь туда же надо вселить и жителя третьей гостиницы.
Настала моя очередь показать, что не зря в Звездной академии пять лет изучают математику.
- Воспользуйтесь простыми числами! Поселите жителей первой гостиницы в № 2, 4, 8, 16,..., второй — в № 3, 9, 27, 81,..., третьей — в № 5, 25, 125, 625,..., четвертой — в № 7, 49, 343,... .- А не получится ли опять, что в один номер придется помещать двух постояльцев? — спросил директор.
- Нет! Ведь если взять два простых числа, то никакие их степени с натуральными показателями не могут оказаться равными. Если p и q — простые числа, причем p≠q, а m и n — натуральные числа, то pm≠qn.
Директор согласился со мной и тут же нашел усовершенствование предложенного способа, при котором использовались лишь два простых числа: 2 и 3. Именно, он предложил поселить жильца из m-го номера n-й гостиницы в номер 2m3n. Дело в том, что если m≠p или n≠q, то 2m3n≠2p3q. Поэтому в один и тот же номер пе поселятся двое.
Это предложение привело всех в восторг. Была решена задача, всем казавшаяся неразрешимой. Но премии не получил ни я, ни директор — при наших решениях слишком много номеров оставались пустыми (у меня такие номера, как 6, 10, 12, и вообще все номера, которые не были степенями простых чисел, а у директора номера, которые нельзя записать в виде 2m3n). Самое лучшее решение предложил один из филателистов — президент Математической академии галактики Лебедя.
Он посоветовал сначала составить таблицу, занумеровав ее строки номерами гостиниц, а столбцы — номерами комнат. Например, на пересечении четвертой строки и шестого столбца записывается шестая комната четвертой гостиницы. Вот эта таблица (вернее, ее левая верхняя часть, так как для записи всей таблицы надо бесконечно много строк и столбцов):
- А теперь расселяйте обитателей по квадратам,- сказал математик-филателист.
- Как?- не понял директор.
- По квадратам! В № 1 поселяется жилец из (1,1), то есть из первого номера первой гостиницы; в № 2 — из (1,2), то есть из второго номера первой гостиницы; в № 3 — из (2,2) — второго номера второй гостиницы и в № 4 — из (2,1) — первого номера второй гостиницы. Тем самым будут расселены жильцы из верхнего левого квадрата со стороной 2. После этого в № 5 поселяем жильца из (1,3), в № 6 — из (2,3), в № 7 — из (3,3), в № 8 — из (3,2), в № 9 — из (3,1). (Эти номера образуют квадрат со стороной 3.)
И, взяв листок бумаги, он набросал на нем следующую схему расселения:
- Неужели для всех хватит места?- усомнился директор.
- Конечно. Ведь в первые n2 номеров мы поселяем при этой схеме жильцов из первых п номеров первых п гостиниц. Поэтому рано или поздно каждый жилец получит номер. Например, если это жилец из № 136 гостиницы № 217, то он получит номер на 217-м шагу. Легко даже сосчитать этот номер. Он равен 2172 — 136 + 1. Вообще, если жилец занимает номер n в m-й гостинице, то при n≥m он займет номер (n-1)2 + m, а при n
Предложенный проект и был признан наилучшим: все жители из всех гостиниц были поселены в нашей гостинице и ни один ее номер не пустовал. Математику-филателисту досталась премия — туристическая путевка в галактику ЛЦР-287.
В честь столь удачного размещения директор гостиницы устроил прием, на который пригласил всех ее жильцов. Этот прием также не обошелся без осложнений. Обитатели комнат с четными номерами задержались на полчаса, и, когда они появились, оказалось, что все стулья заняты, хотя гостеприимный хозяин поставил по стулу на каждого гостя. Пришлось подождать, пока все пересели на новые места и освободили необходимое количество стульев (разумеется, ни одного нового стула в зал не внесли). Зато когда стали подавать мороженое, то каждый гость получил по две порции, хотя повар заготовил в точности по одной порции на гостя. Надеюсь, что теперь читатель сам поймет, как все это случилось.
После конца приема я сел в свою фотонную ракету и полетел на Землю. Мне нужно было рассказать всем земным космонавтам о новом пристанище в космосе. Кроме того, я хотел проконсультироваться с виднейшими математиками Земли и моим другом профессором Тарантогой о свойствах бесконечных множеств.
От автора.
На этом мы временно расстанемся с нашим героем. Многое в его рассказе вызывает сомнения — ведь по законам теории относительности невозможно передавать сигналы со скоростью, большей чем 300 000км/с. Поэтому даже самая первая команда администратора потребовала бы для своего выполнения бесконечно большого промежутка времени. Но не будем требовать слишком многого от Иона Тихого — в его путешествиях бывали куда более невероятные приключения.
Дальнейшая часть книги посвящается рассказу о теории бесконечных множеств. И хотя события будут развертываться не в межзвездном пространстве, а на отрезке [0, 1] или квадрате со стороной 1, многие из них окажутся не менее необычайными.
Как сравнивать множества. В начале главы мы занимались вопросами, общими для конечных и для бесконечных множеств. Теперь мы займемся свойствами, характерными только для бесконечных множеств. Из рассказа Иона Тихого уже известно, что эти свойства сильно отличаются от свойств конечных множеств — вещи, невозможные для конечных множеств, оказываются возможными для бесконечных.
Первый вопрос, который мы сейчас разберем, это вопрос о сравнении друг с другом бесконечных множеств. Для конечных множеств самой разной природы всегда можно сказать, какое из них содержит больше элементов, а какое меньше. Для бесконечных же множеств этот вопрос становится гораздо более сложным. Например, чего больше, натуральных чисел или рациональных, рациональных или действительных? Где больше точек, на отрезке или на всей прямой, на прямой или в квадрате?
На первый взгляд кажется, что ответить на эти вопросы совсем просто. Ведь множество натуральных чисел является частью множества рациональных чисел, а отрезок-частью прямой. Не ясно ли, что поэтому натуральных чисел меньше, чем рациональных, а точек на отрезке меньше, чем точек на всей прямой? Оказывается, не ясно. Ведь ниоткуда не следует, что при переходе к бесконечным множествам сохранятся .законы, выведенные из рассмотрения конечных множеств, например закон о том, что "часть меньше целого".
А самое главное, попытка сравнения бесконечных множеств по тому признаку, что одно является частью другого, заранее обречена на неудачу. Например, где больше точек, в квадрате или на всей бесконечной прямой? Ведь ни квадрат нельзя вложить в прямую линию, пи прямую линию нельзя, не ломая ее, поместить в квадрат. Разумеется, можно разломать прямую линию на отрезки, длина которых равна стороне квадрата, и после этого каждый отрезок поместить в квадрат так, чтобы они не пересекались друг с другом. Но вдруг и квадрат можно как-то разбить на части, а потом эти части положить на прямую, чтобы они не задевали друг друга? А сколько есть бесконечных множеств, не являющихся частями друг друга! Множество квадратов на плоскости и множество кругов на той же плоскости не имеют ни одного общего элемента. Как же сравнить их? Как узнать, чего больше во Вселенной — атомов азота или кислорода?
Итак, задача поставлена. В первую очередь мы выясним, в каком случае надо говорить, что одно множество содержит столько же элементов, сколько и второе. Иными словами, выясним, в каких случаях два бесконечных множества имеют "поровну" элементов.
На танцплощадке.
Для конечных множеств задача сравнения решается просто. Чтобы узнать, одинаково ли число элементов в двух множествах, достаточно пересчитать их. Если получатся одинаковые числа, то, значит, в обоих множествах поровну элементов. Но для бесконечных множеств такой способ не годится, ибо, начав пересчитывать элементы бесконечного множества, мы рискуем посвятить этому делу всю свою жизнь и все же не закончить начатого предприятия.