Все номера заняты. Куда поселить новых гостей?

Условие

В математическом отеле номера обозначены всеми положительными целыми числами: $1$ $2$ $3$ …, и в каждом живёт ровно один гость. Прибыла ещё одна бесконечная группа гостей, также пронумерованных $1$ $2$ $3$ …. Можно одновременно назначить всем старым гостям новые номера и затем расселить новых; ограничения времени и реального здания не рассматриваются. Как дать каждому отдельный номер, никого не выселяя из отеля? Нужно явное правило, по которому любой гость узнает свой номер.

О задаче · Подростки и взрослые

Тема: Бесконечность и соответствия
Для кого: Подростки и взрослые
Уровень библиотеки: Продвинутый · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Переселите старых гостей так, чтобы они занимали только чётные номера.

Подсказка 2

Можно ли пронумеровать освободившиеся нечётные номера теми же положительными целыми числами?

Разобрать решение по шагам

Переселите старых гостей

Гостю из номера $n$ назначаем номер $2n$ Разные исходные номера дают разные чётные номера, так что столкновений нет. Любой старый гость получает конкретный конечный номер: например, из $37$ переезжает в $74$ После одновременного переназначения старые гости занимают все чётные номера.

Расселите прибывшую группу

Новому гостю $k$ назначаем номер $2k-1$ Получаются все нечётные номера: первый идёт в $1$ второй в $3$ третий в $5$ Эти номера различны между собой и не заняты старыми гостями. Для каждого нового гостя правило даёт место.

Проверьте смысл результата

Каждый положительный целый номер либо чётный, либо нечётный, поэтому схема описывает весь отель и не требует «последнего свободного номера». Она показывает, что две группы, каждая перечисляемая натуральными числами, можно перечислить одной такой последовательностью. Для конечного отеля тот же перенос не сработает: номера $2n$ могут выйти за границу здания.

Два потока гостей занимают разные номера

01Старый гость n → 2n2, 4, 6, 8, …

02Новый гость k → 2k−11, 3, 5, 7, …

03Чётные и нечётныеникто не получает один номер с другим

Ответ

Нынешнего гостя комнаты $n$ переселить в комнату $2n$ а нового гостя с номером $k$ — в комнату $2k-1$

Главная идея

При работе с бесконечными множествами надёжнее строить явное взаимно однозначное соответствие, чем опираться на бытовую арифметику размеров.

Как заметить эту идею в другой задаче

Бесконечное пронумерованное множество нужно освободить для ещё одного такого множества. Разделите номера на непересекающиеся бесконечные подпоследовательности и задайте явное переселение.

Возможная ошибка

Предложить поселить новых гостей «после последнего номера». Последнего положительного целого числа не существует.

Источник и примечания

Источник и редакция

Классическая задача. Формулировка и разбор — Popov Academy.

Проверь себя

Прибыли только семь новых гостей. Как освободить для них ровно первые семь номеров простым правилом?

Ответ к дополнительной задаче

Старого гостя из номера $n$ переселить в $n+7$ Тогда старые займут номера $8,9,10,\ldots$ а новые семь гостей — номера от $1$ до $7$ Разные старые номера остаются разными, и ни один старый гость не теряет места.

Продолжить тему: Подсчёт вариантов →

Тема, знания и приёмы

Подсчёт вариантов · Начальный вход

Чётные и нечётные натуральные числа
Правило нумерации

Приёмы решения: Симметрия и попарное соответствие

Задать вопрос по задаче →

Условие

Переселите старых гостей

Расселите прибывшую группу

Проверьте смысл результата

Источник и редакция

Условие

Дополнительная задача