Кімнати пронумеровані 1, 2, 3 і так далі без кінця: за кожною кімнатою є наступна. У кожній живе рівно один гість. Пізно ввечері приходить ще один. Менеджер не може нікого виселити й не може поселити двох в одну кімнату, але може попросити гостей перейти в інші номери. Чи поселить він новенького?
Менеджер оголошує: «Кожен, перейдіть із кімнати n у кімнату n + 1». Ніхто не залишається без номера, бо за кожною кімнатою є наступна, а кімната 1 звільняється. Повний нескінченний готель може прийняти ще гостя, нескінченний автобус і навіть нескінченно багато автобусів. Але є гості, для яких місця не знайдеться ніколи.
Цей уявний готель придумав німецький математик Давид Гільберт, щоб показати, чим нескінченні множини відрізняються від скінченних. Таких готелів не буває, але міркувати про них можна так само строго, як про звичайні.
Кімнати пронумеровані 1, 2, 3, 4 і так далі. Номери не закінчуються: за кожною кімнатою є наступна, а останньої кімнати немає.
У кожній кімнаті живе рівно один гість. Вільних кімнат немає, на дверях табличка «Місць немає».
Нікого не можна виселити, і двоє не можуть жити в одній кімнаті. Але менеджер може оголосити по гучномовцю одне правило переїзду, наприклад «гість із кімнати n іде в кімнату …», і всі гості переходять одночасно.
Приходить ще один гість. Чи може менеджер дати йому окрему кімнату так, щоб кожен старий гість теж мав свою кімнату?
«Повний означає повний: вільної кімнати немає, тож новому гостеві ніде жити»
У звичайному готелі так і є: гостеві з останньої кімнати нікуди переходити. У нескінченному готелі останньої кімнати немає, тож усі можуть зсунутися на одну, і кімната 1 звільняється.
Готель повний, кімнат нескінченно багато, виселяти не можна. Оберіть відповідь, перш ніж читати далі.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
У звичайному повному готелі на 100 кімнат новий гість не поміститься: гостеві з кімнати 100 нікуди переходити. Чи є такий «гість з останньої кімнати» в нескінченному готелі?
Гостей не можна виселяти, але можна попросити перейти в інші кімнати, усіх разом. Якщо кожен піде в іншу кімнату, чи може якась кімната звільнитися, а ніхто не лишитися без номера?
Спробуйте правило «з кімнати n у кімнату n + 1». Хто тоді житиме в кімнаті 5? А в кімнаті 1?
Чотири вечори, і щоразу гостей більше. Оберіть правило переїзду або впишіть своє й оголосіть його. Анімація покаже перші кімнати коридору, а перевірка шукає серед сотень тисяч гостей когось без кімнати чи двох у одній. Кнопка «Зламати правило» перевіряє саме ваше правило.
Спершу дайте відповідь у раунді 1: гра її показує.
Кожен гість цього вечора має замість імені нескінченний рядок з 0 і 1, і всі можливі рядки різні гості. Складіть список, хто в якій кімнаті. Клацніть цифру, щоб змінити її, або візьміть готовий список.
Тут немає випадковості, тож замість симуляції комп'ютер чесно перевіряє правило на перших N кімнатах і перших N гостях: хто де опинився, чи є кімнати з двома гостями, чи є гості без кімнати. Поруч точна відповідь, отримана міркуванням для всіх гостей одразу. Подивіться, де вони розходяться.
Спершу дайте відповідь у раунді 1: перевірка її показує.
Скінченна перевірка не є доведенням. Правило «старі гості в n + 1000» проходить перевірку на 1000 кімнатах і ламається на кімнаті 1001. А правило «пасажири по одному» на будь-якій скінченній кількості пасажирів працює, і лише нескінченний автобус лишає всіх без кімнати. Довести правило можна лише міркуванням: показати, хто живе в кожній кімнаті m і що цей гість один.
«Повний» і «немає місця» означають одне й те саме лише тоді, коли кімнат скінченно багато. Уся задача тримається на тому, що в нескінченному коридорі немає останньої кімнати.
Шар «На пальцях» приховано на всіх задачах.
Уявіть шеренгу людей, що не має кінця. Команда «кожен на крок уперед»: перша людина стає на місце другої, друга на місце третьої, і так далі. Ніхто не лишається без місця, бо попереду кожного завжди є ще одне місце. А перше місце звільняється.
Це ще не все пояснення: так поміщається один гість чи будь-яке скінченне число гостей. Для нескінченного автобуса потрібен інший трюк, він у наступних картках.
У готелі на 100 кімнат зробіть те саме: гість із кімнати 99 іде в 100, а гостю з кімнати 100 іти нікуди. Хоч яке правило ви оберете, 101 людину в 100 кімнат по одній не поселиш. У нескінченному готелі такого «гостя з кімнати 100» просто немає: хоч кого ви назвете, у нього є наступна кімната.
Якщо пасажирів нескінченно багато, зсув на одну кімнату не допоможе: зсуватися довелося б без кінця. Натомість гість із кімнати n іде в кімнату 2n. Усі старі гості опиняються в парних кімнатах, кожен у своїй, а всі непарні кімнати 1, 3, 5, … звільняються. Пасажир із місця s іде в кімнату 2s − 1. Виходить дивне: парних номерів «стільки ж», скільки всіх.
Шар «Строго» приховано на всіх задачах.
Щоб перевірити, що стільців у залі стільки ж, скільки людей, рахувати не обов'язково: досить посадити всіх, по одному на стілець, і подивитися, чи не лишилося зайвих. Таке розбиття на пари математики називають бієкцією. Для нескінченних множин це єдиний чесний спосіб порівняти розмір: дві множини однаково великі, якщо їх можна розбити на пари без залишку.
Множину, яку можна пронумерувати 1, 2, 3, …, тобто поселити в готель Гільберта по одному в кімнату, називають зліченною. Гості готелю, гості плюс один, гості плюс автобус і навіть гості плюс нескінченно багато автобусів складають зліченні множини, тому вміщаються.
Запишіть усіх у таблицю: рядок 0 для старих гостей, рядок b для автобуса b, стовпець для номера місця. Рядки нескінченні, і рядків нескінченно багато, тож іти рядком за рядком не можна: перший рядок ніколи не скінчиться. Зате кожна діагональ скінченна: 1 клітинка, потім 2, потім 3. Ідіть діагоналями й роздавайте кімнати 1, 2, 3, … по черзі. Кожен гість у таблиці колись отримає свою кімнату.
Один новий гість: старі гості зсуваються, новий іде в кімнату 1. Кожна кімната m ≥ 2 має рівно одного мешканця, гостя з кімнати m − 1.
Нескінченний автобус: парні кімнати старим гостям, непарні пасажирам.
Нескінченно багато автобусів (b = 0 для старих гостей, місця s = 1, 2, 3, …): обхід діагоналями. Діагональ d = b + s − 1 має d + 1 клітинку, перед нею вже роздано 1 + 2 + … + d кімнат.
Інший відомий спосіб: кожне число m ≥ 1 однозначно записується як степінь двійки, помножений на непарне число. Автобус b отримує кімнати 2b, 3·2b, 5·2b, …
Множини A і B однаково великі (рівнопотужні), якщо існує бієкція між ними. Множина зліченна, якщо вона рівнопотужна множині натуральних чисел ℕ.
Шар «Глибше» приховано на всіх задачах.
Клацайте цифри. Перший рядок під таблицею збирається з діагоналі, у якій кожну цифру замінили на протилежну. Він відрізняється від рядка 1 першою цифрою, від рядка 2 другою, від рядка k k-ю. Тож його немає в жодній кімнаті, хоч який список скласти. Нескінченних рядків з 0 і 1 більше, ніж кімнат: таку множину називають незліченною.
Цей аргумент Георг Кантор опублікував 1891 року. Незліченність дійсних чисел він довів ще 1874 року, іншим способом.
Гільберт розповів про готель у популярному курсі лекцій про нескінченне в Геттінгені взимку 1924–1925 років. Конспект записав його асистент, фізик Лотар Нордгайм. У Гільберта є і один новий гість (зсув на 1), і нескінченно багато нових (кімната n → 2n), а поряд з готелем такий самий приклад про нескінченний бал, де для кожної нової дами знаходиться партнер.
Сам Гільберт готелю не публікував. Його конспект вийшов друком лише 2013 року, а широко відомим готель зробив фізик Георгій Гамов у книжці «Один, два, три… нескінченність» 1947 року. Історію з'ясував історик науки Гельге Краг у статті 2014 року. Спершу він вважав автором Гамова, а потім, дізнавшись про конспект Гільберта, сам спростував цю думку.
Готель веде у три світи. У математиці він ділить нескінченності на зліченні й незліченні: дроби вміщаються, дійсні числа ні. У логіці показує, що частина може бути «такою самою великою», як ціле. А на практиці той самий діагональний трюк доводить, що жодна програма не перевірить кожну програму на зависання.
Математика
Дріб p/q стоїть у рядку p і стовпці q, тож дроби утворюють ту саму нескінченну таблицю, що й автобуси. Обходимо її діагоналями, а клітинки на кшталт 2/2 чи 2/4 пропускаємо: це ті самі 1 і 1/2. Кожен додатний дріб отримає свою кімнату. Нуль і від'ємні дроби теж вміщаються: 0 у кімнату 1, далі по черзі дріб і мінус дріб. Отже, раціональних чисел зліченно багато, хоча між будь-якими двома з них є безліч інших.
З дійсними числами так не вийде. Запишіть число від 0 до 1 у двійковій системі: це нескінченний рядок з 0 і 1, як імена гостей четвертого вечора. Діагональ Кантора знаходить число, якого немає в жодному списку. Є невелике застереження: деякі числа мають два записи, як 0,0111… = 0,1000…, але його легко обійти. Дійсних чисел незліченно багато, і їх не поселить жоден менеджер.
Логіка
Оберіть частину номерів, наприклад лише квадрати 1, 4, 9, 16, … Гостя з кімнати n можна поселити в кімнату n·n, і всі гості поміщаються лише в кімнати-квадрати, по одному. Квадратів серед перших 100 чисел лише 10, а серед перших мільйона тисяча. Та пар з усіма числами їм вистачає.
1638 року Галілей у «Бесідах про дві нові науки» вустами свого героя Сальвіаті помітив саме це про квадрати і зробив висновок, що слова «більше», «менше» й «дорівнює» до нескінченних кількостей не застосовні. Математики пішли іншим шляхом: залишили «дорівнює» у сенсі пар один до одного й погодилися, що частина може дорівнювати цілому. 1888 року Ріхард Дедекінд навіть зробив це означенням: множина нескінченна, якщо її можна розбити на пари з її власною частиною. У скінченній множині частина завжди менша за ціле.
Практика
У таблиці рядки означають програми, стовпці вхідні числа, а клітинка каже, чи зупиняється програма на цьому вході, чи працює вічно. Програма «Навпаки» дивиться на діагональ і робить протилежне: на вході k вона зупиняється, якщо програма k на вході k працює вічно, і зациклюється, якщо та зупиняється. Тож «Навпаки» відрізняється від кожної програми в таблиці хоча б на одному вході, як рядок Кантора.
Тепер припустімо, що хтось написав перевірник, який про будь-яку програму на будь-якому вході правильно каже, зупиниться вона чи ні. Тоді «Навпаки» можна було б написати як звичайну програму: спитай перевірник і зроби протилежне. Але всі програми можна пронумерувати, як гостей, і «Навпаки» мала б свій номер k. На вході k вона мусила б і зупинитися, і не зупинитися. Отже, такого перевірника не існує. Цю ідею, яку сьогодні вчать як проблему зупинки, Алан Тюрінг виклав у статті 1936 року.
На практиці це означає, що компілятори, аналізатори коду й антивіруси завжди чогось не знають: вони або пропускають частину зависань, або іноді даремно б'ють на сполох, або ставлять обмеження часу. Ідеальний перевірник неможливий не через брак швидкості, а через логіку.
У лекціях взимку 1924–1925 років у Геттінгені Гільберт навів два приклади: готель і бал, де всі кавалери вже запросили дам, але для нової дами партнер однаково знаходиться. Висновок він зробив соціальний: у світі з нескінченною кількістю будинків і мешканців не було б бездомних.
4 червня 1925 року в Мюнстері Гільберт повторив ідеї тих лекцій у промові «Про нескінченне», уже без готелю. Звідти його знаменита фраза: ніхто не вижене нас із раю, який створив для нас Кантор. Водночас він казав, що в самій природі нескінченності немає.
Найдавніша відома друкована згадка готелю з'явилася не в Гільберта, а в підручнику з математичного аналізу Отто Гаупта й Георга Аумана. Там без імені Гільберта питають, як поселити нескінченно багато нових гостей у повний нескінченний готель.
Георгій Гамов переказав готель у книжці «Один, два, три… нескінченність» і в примітці послався на «неопубліковану і навіть не написану» «Повну збірку історій про Гільберта» Ріхарда Куранта. Гамов улітку 1928 року працював у Геттінгені й, імовірно, там і почув цю історію.
За три століття до Гільберта Галілей помітив, що кожному числу відповідає його квадрат, тож квадратів «стільки ж», скільки чисел, хоча більшість чисел квадратами не є. Він вирішив, що порівнювати нескінченні кількості не можна. Кантор показав, що можна, і що нескінченності бувають різні.
Конспект лекцій 1924–1925 років увійшов до тому «Лекції Давида Гільберта з основ арифметики й логіки, 1917–1933» за редакцією Вільяма Евальда й Вільфріда Зіга. Лише після цього стало ясно, що готель справді придумав Гільберт.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Для всіх» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.