The paradox of the Grand Hotel

The Grand Hotel paradox is a thought experiment illustrating the properties of infinite sets . He demonstrates a hotel with an infinite number of rooms, each of which has a guest. At the same time, you can always add more visitors to the hotel, even if there are an infinite number of them. The paradox was first formulated by the German mathematician David Hilbert in 1924 and popularized in the book of George Gamow, “One, Two, Three ... Infinity” in 1947 ^[1] ^[2] .

Content

Paradox

Guest ω comes to the hotel, in which all rooms are occupied. In order to free his room, the guest from room 1 goes to room 2, the guest from room 2 - to room 3 and so on. And the new guest ω settles in room 1.

Imagine a hotel with a countable number of rooms, each of which has a guest. At first glance, it is impossible to accommodate new visitors to the hotel, as if it was a regular hotel, with a finite number of rooms.

New Visitor

In order to add a new person, we have to free one room. To do this, we will move the guest from room No. 1 to room No. 2, the guest from room No. 2 will move to room No. 3, and so on. In general, a guest from room n will move to room n + 1. Thus, we will free the first room in which it will be possible to accommodate a new guest.

Endless New Visitors

In this case, we will have to free an infinite number of rooms: we move the guest from room x to a room whose number is 2 in degree x. We add new visitors in the same way, only raising to the power not 3, but 3.

An infinite number of buses with an infinite number of passengers

There are several ways to resettle an infinite number of passengers from an infinite number of buses. Most methods imply that each passenger has a seat number on which he sits in his bus. In the future, we denote the seat number of the variable n, and the number of the bus in which the passenger sits, the variable c.

An infinite number of linguists with a favorite word from the letters of the Russian alphabet

The rooms are released in the same way as in the case when you need to share an infinite number of visitors. Then we encode the favorite word of each linguist by letters: a = 1, b = 2, c = 3 .. i = 33. Thus, the linguist with the favorite word "I" will receive the code "33". If the codes match, you need to ask these 2, or 3, or 4 linguists to say their favorite words, for example, "I" and "cc", one of them should be placed in the room in which he was supposed to settle, and the second should be placed in a room whose number is the next prime number in the power of the code.

Prime Degree Method

To begin with, we move all the guests from our rooms to rooms of degree 2. Thus, the person from the room $i$ ${\ displaystyle i}$ will now be in the room $2^{i}$ ${\ displaystyle 2 ^ {i}}$ . All passengers from the first bus will be accommodated in rooms under the number $3^{n}$ ${\ displaystyle 3 ^ {n}}$ , from the second bus to rooms at number $5^{n}$ ${\ displaystyle 5 ^ {n}}$ . Bus passengers $c$ ${\ displaystyle c}$ put in rooms $p^{n}$ ${\ displaystyle p ^ {n}}$ where $p$ ${\ displaystyle p}$ - $c$ ${\ displaystyle c}$ odd prime number . According to the basic theorem of arithmetic (see the article The Basic Theorem of Arithmetic ), the numbers will not coincide. This solution leaves rooms whose numbers are not a power of a prime number , that is, most difficult numbers: 6, 10, 12, 14, 15, 18, 20, 21, 22, etc.

Integer Factorization Method

Every guest who sits in place $n$ ${\ displaystyle n}$ in the bus $c$ ${\ displaystyle c}$ can be lodged in a room $2^{n}3^{c}$ ${\ displaystyle 2 ^ {n} 3 ^ {c}}$ (the hotel can be designated as a zero bus). For example, a guest from room 2592 ( $2^{5}\times 3^{4}$ ${\ displaystyle 2 ^ {5} \ times 3 ^ {4}}$ ) was in 4 bus and sat in 5th place. Since each number has a unique decomposition into a product of prime factors, not one of the guests will be left without a room and no one will be placed in a busy room. As in the previous method, in this case there are free rooms.

Alternation Method

For each guest, the lengths of his bus numbers and their place in any positional number system are compared. If one of the numbers is shorter, leading zeros are added to it until both numbers have the same number of digits. Alternating the numbers of these numbers, we get the room number. For example, a passenger on a seat 6917 in bus 843 will receive room number 6 0 9 8 1 4 7 3 , i.e. 60981473.

Unlike a solution with powers of prime numbers, the alternation method fills the hotel completely without leaving empty rooms.

Triangular Number Method

In the beginning, each resident of the hotel will be relocated from the room $n$ ${\ displaystyle n}$ to the room $T_{n}$ ${\ displaystyle T_ {n}}$ (those. $n$ ${\ displaystyle n}$ triangular number ${\frac {n(n+1)}{2}}$ ${\ displaystyle {\ frac {n (n + 1)} {2}}}$ ). Next, guests who sit in place $n$ ${\ displaystyle n}$ in the bus $c$ ${\ displaystyle c}$ will be settled in the room $T_{c+n-1}+n$ ${\ displaystyle T_ {c + n-1} + n}$ . Thus, all rooms will be occupied, and in each room there will be only one resident.

Higher Infinity Levels

Let's say that the hotel is on the seashore. An infinite number of car ferries arrive on the shore, each of which has an infinite number of buses, each with an infinite number of passengers. This situation, including three “levels” of infinity, is solved by expanding any of the methods presented above. In this case, it is also understood that the ferries have serial numbers.

Next, the designation of the passenger address will be used in the form of "place-bus-ferry". For example, 768-85-7252 is the address of the passenger in 768th place in the 85th bus on the 7252nd ferry.

The integer factorization method can be applied by adding a new prime: a passenger seated $n$ ${\ displaystyle n}$ in the bus $c$ ${\ displaystyle c}$ on a ferryboat $f$ ${\ displaystyle f}$ will be settled in the room $2^{n}3^{c}5^{f}$ ${\ displaystyle 2 ^ {n} 3 ^ {c} 5 ^ {f}}$ . This method returns very large numbers for small input. For example, a passenger with the address 10-45-26 will occupy the room 4507923441392263334111022949218750000000000 ( $2^{10}\times 3^{45}\times 5^{26}$ ${\ displaystyle 2 ^ {10} \ times 3 ^ {45} \ times 5 ^ {26}}$ ). As noted earlier, the method leaves a huge number of rooms empty.

The alternation method can be used alternating not in three digits, but in three. So, a passenger with an address 1-2-3 will occupy room 123, and a passenger with an address 42609-233-7092 will occupy room 400207620039932.

Anticipating the possibility of any level of infinity, the hotel will wish to assign rooms in such a way that residents do not need to move when new guests check in. One of the possible solutions is to assign a binary number to the guests, where the units divide the groups of zeros, in each group the number of zeros is equal to the corresponding number from the guest address, for each level of infinity. For example, a guest with the address 2-5-4-3-1 will be accommodated in room 10010000010000100010, which corresponds to the decimal number 590882.

As a complement to this method, one zero is removed from each group of zeros. Thus, the guest with the address 2-5-4-3-1 will be occupied by the room 101000010001001, which corresponds to the decimal 10308. This addition ensures that each room will be occupied by the guests.

Analysis

The Hilbert Paradox is indeed a paradox. The expressions “every room has a guest” and “guests can no longer be accommodated” lose their equivalence when it comes to an infinite number of rooms.

The properties of finite and infinite sets are significantly different. The Grand Hotel paradox can be understood using Cantor’s theory of transfinite numbers. In a regular (endless) hotel with more than one room, the number of odd rooms is obviously less than the total number of rooms. However, at the Hilbert Grand Hotel the number of odd numbers is no less than the total number of rooms. In mathematical terms, the power of a subset containing odd rooms is equal to the power of the set of all rooms. Indeed, infinite sets are characterized as sets having their own subsets of the same cardinality.

Notes

↑ Kragh, Helge. The True (?) Story of Hilbert's Infinite Hotel (Neopr.) . - 2014.
↑ Gamow, George. One Two Three ... Infinity: Facts and Speculations of Science. - New York: Viking Press, 1947 .-- P. 17.

Links

The paradox of an endless hotel
Paradox solution
http://spbtym.ru/ Problem number 2 of 1 open Tournament of Young Mathematicians grade 5-8.

[1] Kragh, Helge. The True (?) Story of Hilbert's Infinite Hotel (Neopr.) . - 2014.

[2] Gamow, George. One Two Three ... Infinity: Facts and Speculations of Science. - New York: Viking Press, 1947 .-- P. 17.