3. Let's consider 20 statements:

| "I have exactly one sister." | "I have exactly one brother." |
| :--- | :--- |
| "I have exactly two sisters." | "I have exactly two brothers." |
| "I have exactly ten sisters." | "I have exactly ten brothers." |

a) Each of the four siblings made a different one of these 20 statements. Is it possible that all four were telling the truth?

b) Find the largest natural number $n$ such that each of the $n$ siblings can make a different one of these 20 statements and be telling the truth.

(Josef Tkadlec)
SOLUTION. a) Yes, it is possible. In the case where the four siblings are two brothers and two sisters, they can truthfully make four mutually different statements. One brother says: "I have exactly one brother" and the other: "I have exactly two sisters," one sister says: "I have exactly one sister" and the other: "I have exactly two brothers."

b) For $n=4$, we have found that each of the four siblings can make a different true statement.

In the case of $n \geqq 5$, there are at least three siblings of the same gender. Suppose each of them truthfully states the number of their sisters or brothers. Then, however, at least two of these statements will be the same (those about the number of sisters, or those about the number of brothers). Therefore, no integer $n \geqq 5$ has the required property.

Conclusion. The largest suitable $n$ is 4.

COMMENT. In part b) of the given solution, we used a fact known as the **Dirichlet principle** or the **pigeonhole principle**. It states, for example, that if we distribute 13 items into 2 containers, at least one container will have at least 7 items. Or if we distribute 13 items into 3 containers, at least one container will have at least 5 items. Or when distributing $2n+1$ items into 2 containers, at least one container will have at least $n+1$ items. Generally, when distributing at least $kn+1$ items into $k$ containers, at least one container will have at least $n+1$ items (we wrote this above for $k=2$ and $n=6$, as well as for $k=3$ and $n=4$, and for $k=2$ and general $n$). The "items" can be numbers, geometric shapes, people, statements, essentially anything. The containers can then represent any properties of the individual items. For example, we often divide integers into 2 containers based on whether they are even or odd (see introductory problem N2).

In our solution, we used the Dirichlet principle twice, each time for 2 containers. In the first case, the siblings played the role of "items" and gender (male/female) played the role of "containers". In the second case, the "items" were the statements and the "containers" were statements about sisters and statements about brothers.

NOTE. Let's show that the explanation of part b) of the solution can also be presented differently. If in a given group of $n$ siblings there are exactly $B$ brothers and exactly $S$ sisters, each of them can truthfully make only one of the following four statements (the first two are statements by brothers, the remaining two are statements by sisters):