How about infinitely many very long buses with seats numbered \(1,2,3...\), each carrying infinitely many guests, all arriving at the hotel. Assume for now that the hotel is empty. But that seems like a lot of guests to accommodate. What should you do?
The whole idea of problems with Hilbert’s Hotel is about assigning numbers to elements of an infinite set. We say that a set of items is countable if and only if we can give all the items of the set as gifts to the guests at the Hilbert’s hotel, and each guest gets at most one gift. In other words, it means that we can assign a natural number to every item of the set. Evidently, the set of all the natural numbers is countable: we gift the number \(n\) to the guest in room \(n\).
The set of all integers, \(\mathbb{Z}\), is also countable. We gift the number \(n\) to the guest in room \(n\). Then we ask everyone to take their gift and move to the room double their original number. Rooms with odd numbers are now free (\(1, 3, 5, 7, \dots\)). We fill these rooms with guests from an infinite bus and gift the number \(-k\) to the guest in room \(2k+1\). Yes, that’s right: the person in the first room will be gifted the number \(0\).
Prove now that the set of all positive rational numbers, \(\mathbb{Q}^+\), is also countable. Recall that a rational number can be represented as a fraction \(\frac{p}{q}\) where the numbers \(p\) and \(q\) are coprime.
Imagine you see a really huge party bus pulling out, an infinite bus with no seats. Instead everyone on board is identified by their unique name, which is an infinite sequence of \(0\)s and \(1\)s. The bus has every person named with every possible infinite sequence of \(0\)s and \(1\)s, someone is named \(00010000..00...\), someone else \(0101010101...\), and so on. Prove that this time you will not be able to accommodate all the new guests no matter how hard you try.
Prove that the set of all real numbers is not countable.
Mr Smith has seven children. He wants to send three of them to run some errands on a Saturday. We will send the first child at 1pm, the second child at 2pm and the third one at 4 pm. In how many ways can he choose them?
Katie is making a bouquet. She has \(12\) different flowers available, but wants her bouquet to be composed of exactly \(5\) of them. The order of the flowers in the bouquet doesn’t matter. In how many ways can she do this?
We have \(6\) digits available: \(1,3,4,5,7\) and \(9\). We wish to make a \(3\)-digit number with different digits but only using these \(6\) digits. How many ways are there of doing this? What if we want the digits within the number to be arranged in an ascending order - how many numbers are left?
David has \(15\) video games in boxes on his shelf. His family is visiting his aunt next week. He was asked to pick only \(4\) games to play on his cousin’s computer. In how many ways can he do this?
Katie is making a bouquet again. She has \(12\) flowers, but this time she wants to use not \(5\), but \(7\) flowers for a bouquet. In how many ways can she do this? How is this answer related to the answer to the previous question about Katie? Why?
Rithika is choosing songs for a party tonight. She has \(214\) songs in her library and wants to use \(50\) for the party. She wants to play each song only once. In how many ways can she compose her playlist?
Now suppose that each song has a different duration, and Rithika wants the songs to play in order from the longest chosen to the shortest chosen. How many ways can she choose her playlist now? (You can leave the answer as a formula).