In a class there are 50 children. Some of the children know all the letters except “h” and they miss this letter out when writing. The rest know all the letters except “c” which they also miss out. One day the teacher asked 10 of the pupils to write the word “cat”, 18 other pupils to write “hat” and the rest to write the word “chat”. The words “cat” and “hat” each ended up being written 15 times. How many of the pupils wrote their word correctly?
A hostess bakes a cake for some guests. Either 10 or 11 people can come to her house. What is the smallest number of pieces she needs to cut the cake into (in advance) so that it can be divided equally between 10 and 11 guests?
a) A square of area 6 contains three polygons, each of area 3. Prove that among them there are two polygons that have an overlap of area no less than 1.
b) A square of area 5 contains nine polygons of area 1. Prove that among them there are two polygons that have an overlap of area no less than \(\frac{1}{9}\).
In a corridor of length 100 m, 20 sections of red carpet are laid out. The combined length of the sections is 1000 m. What is the largest number there can be of distinct stretches of the corridor that are not covered by carpet, given that the sections of carpet are all the same width as the corridor?
How many subsets of \(\{1, 2, . . . , n\}\) are there of even size?
In how many ways can \(\{1, . . . , n\}\) be written as the union of two sets? Here, for example, \(\{1, 2, 3, 4\}\cup\{4, 5\}\) and \(\{4, 5\}\cup\{1, 2, 3, 4\}\) count as the same way of writing \(\{1, 2, 3, 4, 5\}\) as a union.
Prove for any natural number \(n\) that \((n + 1)(n + 2). . .(2n)\) is divisible by \(2^n\).
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.