In good conditions, bacteria in a Petri cup spread quite fast, doubling every second. If there was initially one bacterium, then in \(32\) seconds the bacteria will cover the whole surface of the cup.
Now suppose that there are initially \(4\) bacteria. At what time will the bacteria cover the surface of the cup?
A piece containing exactly \(4\) black cells is cut out from a regular \(8\) by \(8\) chessboard. You are only allowed to cut along the edges of the cells and the piece must be connected - namely you cannot have cells attached only with a vertex, they have to share a common edge.
Find the largest possible area of such a piece.
Prove that the set of all finite subsets of natural numbers \(\mathbb{N}\) is countable. Then prove that the set of all subsets of natural numbers is not countable.
In a distant village, there are \(3\) houses and \(3\) wells. Inhabitants of each house want to have access to all \(3\) wells. Is it possible to build non-intersecting straight paths from each house to each well? All houses and well must be level (that is, none of them are higher up, like on a mountain, nor are any of them on lower ground, like in a valley).
Today you saw two infinitely long buses with seats numbered as \(1,2,3,...\) carrying infinitely many guests each arriving at the full hotel. How do you accommodate everyone?
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.