Problems

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.

Prove the triangle inequality: in any triangle \(ABC\) the side \(AB < AC+ BC\).

In certain kingdom there are a lot of cities, it is known that all the distances between the cities are distinct. One morning one plane flew out of each city to the nearest city. Could it happen that in one city landed more than \(5\) planes?

Find all \(n\) such that a closed system of \(n\) gears in a plane can rotate. We call a system closed if the first gear wheel is connected to the second and the \(n\)th, the second is connected to the first and the third, the third is connected to the second and the fourth, the fourth is connected to the third and the fifth, and so on until the \(n\)th is connected to the \(n-1\)th and the first. In the picture, we have a closed system of three gears.

There are various ways to prove mathematical statements. One of the possible methods which might come in handy in certain situations is called proof by contradiction. To prove a statement we first assume that the statement is false and then deduce something that contradicts either the condition, or the assumption itself, or just common sense. Due to the contradiction, we have to conclude that the first assumption must have been wrong, so the statement is actually true.

A closely related method is called contrapositive proof. An example should make the idea quite clear. Consider the statement “if the joke is funny, then I will be laughing". Another completely equivalent way of saying it would be “if I am not laughing, then the joke is not funny". The second statement is known as the contrapositive of the first statement.

We can often prove a statement by proving its contrapositive. Many statements are proven by deriving a contradiction. However, one can often rewrite them as either a direct proof or a contrapositive proof.

Let’s take a look at both of these techniques.

Could you meet a person inhabiting this planet who asks you “Am I a Goop?"

On this planet you meet a couple called Tom and Betty. You hear Tom ask someone: “Are Betty and I both Goops?"
What kind is Betty?