17/01/2024

Note: this article was originally published in Cantor’s Paradise.

Hilbert’s Hotel: You’re Missing the Best Bit!

Infinity, enumerating the rationals and elegant solutions to innocuous problems.

”The infinite! No other question has ever moved so profoundly the spirit of man.” - David Hilbert

Hilbert’s hotel paradox is a beautiful demonstration of the countably infinite. A coach full of the natural numbers, stretching backwards forever, arrives at a hotel with endless rooms and a maths-wizz receptionist. After allocating every guest a room the receptionist returns to her desk only to find another set has arrived! A brief negotiation almost always allows the receptionist to rearrange the current guests, leaving room for the newest. The details of these theoretical negotiations can be both ingenious and infuriating. In building his hotel in 1924 David Hilbert created a brilliant framework for discussing the mathematics and philosophy of infinity.

As is often the case, this paradox is in fact anything but. It can be shown that any coach of numerical guests either can or cannot fit into the hotel, thereby making the set of guests either countably or uncountably infinite. Many treatments of the Hilbert’s hotel ‘paradox’ have the following structure:

1 - An infinite number of guests are staying in an infinite hotel.

2 - One more guest arrives and manages to find a room.

3 - An infinite number of guests arrive and find rooms.

4 - An infinite number of coaches arrive, each containing an infinite number of guests, rooms are found for all of them.

5 - Voilà!

This setup serves to deliver the main point, that infinity is counter-intuitive but not impossible to work with. However, considering a seemingly mundane sub-problem where an infinite quantity of rational numbers (those numbers that can be expressed as the division of two integers) arrive on a single coach leads to some fascinating conclusions.

At first glance, there would appear to more rational numbers than natural. After all, taking the reciprocal of the natural numbers gives us an infinity of values between 0 and 1 before we’ve even considered the space between every other pair of natural numbers. However, given the unexpected solutions to the earlier parts of the paradox, a mathematical treatment is clearly required before we can draw any conclusions. So, what is required of our receptionist here to fit these rational guests into the hotel? She needs to find a one-to-one mapping between the set of all rational numbers and the set of all natural numbers. Namely, a bijection.

A good starting point is to create a grid of values where the axes each correspond to the natural numbers. Each square in the grid can then be labelled with the fraction x/y. Drawing a snaking line through each of these squares from the top left and labelling each square with a natural number as we go enumerates the fractions, thus showing that there are at least as many naturals as rationals.

Grid of integers and fractions

The italicised at least should have given you a pretty good idea that this solution is flawed. The problem here is that we have mapped some of the rational guests to multiple rooms, the lucky people! Take for example the grid squares corresponding to fractions 1/2 and 2/4 respectively. Being equivalent, both fractions only refer to one guest. We have given this guest both rooms. In fact, given that there is an infinite number of fractions equivalent to every other fraction our receptionist has unwittingly allocated each guest an infinite number of rooms! To satisfy the criteria of a bijection (and the hotel budget) each guest must be allocated one and only one room.

A trivial way of overcoming this hurdle is to simply skip the fractions in the grid that are equivalent to an already-roomed one. Whilst this works, it is not only untidy but makes it difficult to generalise the result to other areas of interest.

Enter the Stern-Brocot sequence. Discovered by American mathematicians Neil Calkin and Herbert Wilf in 1999*, this sequence meets our criteria exactly. So how do we construct it?

Begin in a similar fashion to the Fibonacci sequence, by adding the ith and (i+1)th digits and appending the result to the end of sequence. However, before moving on also append the (i+1)th digit to the end as well. The first few iterations are shown below, with the (i+1)th digit in red.

Modified Fibonacci sequence

At first this looks fairly random but if we write out a sequence of fractions using the ith digit as the numerator and the (i+1)th as the denominator the result begins to look a lot like a list of rational numbers.

Stern-Brocot series

The Stern-Brocot sequence has some elegant properties. Not only does it contain every conceivable rational number but each appears exactly once, solving our duplicate issue! They are also all guaranteed to be in their simplest form, so no identity crises for our guests.

A further interesting property of the sequence is that the nth value (counting from 0) is equal to the number of ways of writing the number n in binary if you allow the use of 0, 1 and 2 in the base 2 system. Normally, binary representations are unique but adding the 2 allows multiple ways of writing the same number. For example, let n be 6, or 110 in binary. incorporating the two gives us 102 and 022 as well, so three ways in total. Sure enough the 6th value of the sequence is 3.

This part of the Hilbert’s hotel paradox is often skipped over in interest of maintaining the wow factor, but to my mind it’s one of the most beautiful parts of the problem and well worthy of discussion. So, next time someone brings up this hotel and its receptionist, make sure they give its rational visitors a warm welcome.

*The name of the sequence is derived from the Stern-Brocot tree, discovered independently by German number theorist Moritz Stern and Achille Brocot, a French clockmaker. Brocot used it to design systems of gears with a desired gear ratio.

Resources