Problems

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.

Today we will solve some geometric problems using the triangle inequality. This is an inequality between the lengths of the sides of any triangle, or between the distances of any three points.

The shortest path between any two points \(A\) and \(B\) is a straight segment - every other path is longer. In particular, a path through another point, \(C\), is equal or longer. \[AC + BC \ge AB\] The triangle inequality says that the sum of lengths of any two sides of a triangle is always larger than the length of the third side. The inequality only becomes an equality if \(ABC\) is not actually a triangle and the point \(C\) lies on the segment from \(A\) to \(B\).

Even though it is a simple idea, it can be a really helpful tool in problem solving.

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?

Let \(A=\{1,2,3\}\) and \(B=\{2,4\}\) be two sets containing natural numbers. Find the sets: \(A\cup B\), \(A\cap B\), \(A-B\), \(B-A\).

Let \(A=\{1,2,3,4,5\}\) and \(B=\{2,4,5,7\}\) be two sets containing natural numbers. Find the sets: \(A\cup B\), \(A\cap B\), \(A-B\), \(B-A\).

A set is a collection of objects of any specified kind, the objects are called elements or members, the objects in one set cannot repeat, namely \(\{1,2,3\}\) and \(\{1,2,2,2,3\}\) are identical sets. We denote a set by a capital letter \(A\), or \(B\) and write \(x\in A\) if \(x\) is an element of \(A\), and \(x\notin A\) if it is not. The notation \(A=\{a,b,c,...\}\) means that the set \(A\) consists of the elements \(a,b,c,...\). The empty or void set, \(\emptyset\), has no elements. If all elements of \(A\) are also in \(B\), then we call \(A\) a subset of \(B\) and we write \(A\subseteq B\). It is an axiom that the sets \(A\) and \(B\) are equal \(A=B\) if they have the same elements. Namely, \(A\) is a subset of \(B\) and \(B\) is a subset of \(A\) at the same time.
For any sets \(A\) and \(B\), we define their union \(A\cup B\), intersection \(A\cap B\), and the difference \(A-B\) as follows:

• the union \(A\cup B\) is the set of all elements that belong to \(A\) or \(B\);

• the intersection \(A\cap B\) is the set of elements that belong to both \(A\) and \(B\);

• the difference \(A-B\) consists of those \(x \in A\) that are do not belong to \(B\).

Sometimes it is useful to draw sets as Venn diagrams, on the diagram below the pink circle represents the set \(A\), the yellow circle represents the set \(B\), the orange part is the intersection \(A\cap B\), the pink part is \(A-B\), the yellow part is \(B-A\), and the whole picture is the union \(A\cup B\).

Given three sets \(A,B,C\). Prove that if we take a union \(A\cup B\) and intersect it with the set \(C\), we will get the same set as if we took a union of \(A\cap C\) and \(B\cap C\). Essentially, prove that \((A\cup B)\cap C = (A\cap C)\cup (B\cap C)\).