Problems

Now there are finitely many infinitely long buses with seats numbered as $1,2,3,...$ carrying infinitely many guests each arriving at the full hotel. Now what do you do?

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.

We meet a group of people, all of whom are either knights or liars. Knights always tell the truth and liars always lie. Prove that it’s impossible for someone to say “I’m a liar".

We’re told that Leonhard and Carl are knights or liars (the two of them could be the same or one of each). They have the following conversation.

Leonhard says “If $49$ is a prime number, then I am a knight."

Carl says “Leonhard is a liar".
Prove that Carl is a liar.

There are infinitely many couples at a party. Each pair is separated to form two queues of people, where each person is standing next to their partner. Suppose the queue on the left has the property that every nonempty collection of people has a person (from the collection) standing in front of everyone else from that collection. A jester comes into the room and joins the right queue at the back after the two queues are formed.

Each person in the right queue would like to shake hand with a person in the left queue. However, no two of them would like to shake hand with the same person in the left queue. If $p$ is standing behind $q$ in the right queue, $p$ will only shake hand with someone standing behind $q$’s handshake partner. Show that it is impossible to shake hands without leaving out someone from the left queue.

King Hattius has three prisoners and gives them the following puzzle. He will put a randomly coloured hat on each of their heads: red, blue or green. He’ll then give them $10$ seconds for them to each guess their own hat’s colour at the same time.

However! Each prisoner can only see the other two prisoners’ hats, not their own. There are no mirrors in the prison, and they are not allowed to take off their hat, nor talk, mouth, use sign-language, or otherwise communicate with the other two prisoners during those ten seconds.

Hattius tells them that he’ll release them all if at least one correctly guesses their hat’s colour. He gives them an hour to come up with a strategy - what should their strategy be?

Two aliens want to abduct two humans, but aren’t paying attention, so instead run after pigs. They’re all on squares of a $3\times 6$ rectangle, as seen below. On the first move, the aliens move one square horizontally or vertically. Then on the second move, the pigs move horizontally or vertically. The third move is for the aliens, the fourth move is for the pigs, and so on. If an alien lands on a square with a pig on it, then they’ve succeeded. Show that no matter what the pigs do, they’re doomed.