European Girls' Mathematical Olympiad (EGMO) competition problems

Solution:

Let $\mathcal{T}=\{t_{1}, \ldots, t_{n}\}$. The proof proceeds by induction on $n=|\mathcal{T}|$. If $n=1$ and $\mathcal{T}=\{t\}$, choose a group of $t+1$ people and let every pair of two persons play against each other. Then every person has played $t$ games and the conditions of the problem are satisfied.

In the inductive step, suppose that $\mathcal{T}$ has $n \geq 2$ elements $t_{1}<t_{2}<\cdots<t_{n}$. Consider the set
$$\mathcal{T}'=\{t_{n}-t_{n-1}, t_{n}-t_{n-2}, \ldots, t_{n}-t_{1}\} .$$
By the inductive hypothesis, there exists a group $G'$ of $t_{n}-t_{1}+1$ people that satisfies the conditions of the problem for $T'$.

Next construct a group $G''$ of $t_{n}+1$ people by adding $t_{1}$ people who do not know any of the other $t_{n}-t_{1}+1$ people in $G'$. Finally, construct a group $G$ by complementing the knowledge relation in $G''$ : two persons play against each other in $G$ if and only if they do not play against each other in $G''$.

By construction $t \in \mathcal{T}$ if and only if there exists a person in $G''$ that played against exactly $t_{n}-t$ other people (if $t=t_{n}$, choose one of the $t_{1}$ people added to $G'$). That person knows $t_{n}-(t_{n}-t)=t$ other students in $G$, completing the proof.

Solution:

Let $\mathcal{T}=\{t_{1}, \ldots, t_{n}\}$. The proof proceeds by induction on $n=|\mathcal{T}|$. If $n=1$ and $\mathcal{T}=\{t\}$, we choose a group of $t+1$ people such that everyone plays with everyone else. If $n=2$ and $\mathcal{T}=\{t_{1}, t_{2}\}$ with $t_{1}<t_{2}$, divide the $t_{2}+1$ people into groups $A$ resp. $B$ of size $t_{1}$ resp. $t_{2}-t_{1}+1$ such that everyone from group $A$ played with everyone else whereas people from group $B$ only played with the people from group $A$. Then the people from group $A$ resp. $B$ played with exactly $t_{2}$ resp. $t_{1}$ other people.

In the inductive step, suppose that $T$ has $n>2$ elements $t_{1}<\ldots<t_{n}$. Consider the set
$$\mathcal{T}'=\left(\mathcal{T} \setminus\{t_{1}, t_{n}\}\right)-t_{1}=\{t_{n-1}-t_{1}, t_{n-2}-t_{1}, \ldots, t_{2}-t_{1}\}$$
By the induction hypothesis there exists a group $C$ of $t_{n-1}-t_{1}+1$ people that satisfies the conditions of the problem for $T'$. Next add groups $D$ resp. $E$ of $t_{1}$ resp. $t_{n}-t_{n-1}$ people such that people from group $D$ played with everyone else whereas people from group $E$ only played with the people from group $D$. Then the people from group $C$ played with $t$ other people if and only if they played with $t-t_{1}$ many people among $C$, i.e. if and only if $t \in\{t_{2}, \ldots, t_{n-1}\}=\mathcal{T} \setminus\{t_{1}, t_{n}\}$. People from group $D$ resp. $E$ played with $t_{n}$ resp $t_{1}$ people, which completes the proof.

Solution:

The proof proceeds by induction on $|t_{n}|$. If $t_{n}=1$ we have $n=1$ and we can consider two persons that play against each other. Then every player has played 1 game and the conditions of the problem are satisfied.

If $t_{n}>1$ we distinguish the two cases $t_{1}>1$ and $t_{1}=1$.

If $t_{1}>1$ there exists, by the induction hypothesis, a group $A$ of size $t_{n}$ that satisfies the conditions of the problem for $t_{1}'=t_{1}-1, \ldots, t_{n}'=t_{n}-1$. Now add a new person to $A$ and let him/her play against everyone from $A$. The new group will be of size $t_{n}+1$ and there exists a person which has played $t$ games if and only if there exists a person that has played $t-1$ games within $A$, i.e. if and only if $t \in\{t_{1}, \ldots, t_{n}\}$. Hence the conditions of the problem are satisfied.

If $t_{1}=1$ there exists, by the induction hypothesis, a group $B$ of size $t_{n-1}$ that satisfies the conditions of the problem for $t_{2}-1, \ldots, t_{n-1}-1$. Now add a new person $P$ and let him/her play with everyone from group $B$ and a group $C$ of size $t_{n}-t_{n-1}>0$ and let them play with $P$. The new group will be of size $t_{n-1}+1+(t_{n}-t_{n-1})+1=t_{n}+1$. Since person $P$ has played against everyone he will have played $t_{n}$ games. The people in $C$ will have played $1=t_{1}$ games. There exists a person in $B$ that has played $t$ games if and only if there exist a person in $B$ that has played $t-1$ games within $B$, i.e. if and only if $t \in\{t_{2}, \ldots, t_{n-1}\}$. Hence the conditions of the problem are satisfied.

Solution:

We generalize the construction for $\mathcal{T}=\{1, \ldots, n\}$

Construction

Take sets of people $A_{1}, \ldots, A_{n}$. Let all people of $A_{i}$ play chess with all people in $A_{j}$ with $j \geq n-i+1$

Now the number of games played by anyone in $A_{i}$ is
$\left(\sum_{j \geq n-i+1}|A_{j}|\right)$ or $\left(\sum_{j \geq n-i+1}|A_{j}|\right)-1$ if $i \geq n-i+1$.
Now if we start with one person in each $A_{i}$ and two people in $A_{\left\lceil\frac{n}{2}\right\rceil}$. The number of played games for anyone in $A_{i}$ is equal to $i$. In particular this is a construction for $\mathcal{T}=\{1, \ldots, n\}$
Now to get to numbers of general sets $\mathcal{T}$ of size $n$ we can change the sizes of $A_{i}$ but keep the construction.

Variant 1

Observation 1 Adding a person to a set $A_{i}$ increases the number of games played in $A_{j}$ for $j \geq n-i+1$, by exactly one.
Start with the construction above and then add $t_{1}-1$ people to group $A_{n}$, making the new set of games played equal to $\{t_{1}, t_{1}+1, \ldots, n+t_{1}-1\}$. Then add $t_{2}-t_{1}-1$ to $A_{n-1}$ to get set of games played to $\{t_{1}, t_{2}, t_{2}+1, \ldots, n+t_{2}-2\}$ and repeat until we get to the set $\mathcal{T}$ adding a total of $\sum_{j=1}^{n} t_{j}-t_{j-1}-1=t_{n}-n$ people (let $t_{0}=0$ ), so we get $t_{n}+1$ people in the end.
Clearly we can start by adding vertices to $A_{1}$ or any other set instead of $A_{n}$ first and obtain an equivalent construction with the same number of people.

Variant 2

It is also possible to calculate the necessary sizes of $A_{i}$'s all at once. We have by construction the number of games played in $A_{1}$ is less than the number of games played in $A_{2}$ etc. So we have that in the end we want the games played in $A_{i}$ to be exactly $t_{i}$.
So $(t_{1}, t_{2}, t_{3}, \ldots, t_{n}) \stackrel{!}{=}( |A_{n}|, |A_{n}|+|A_{n-1}|, \ldots, (\sum_{j=2}^{n}|A_{j}|)-1, (\sum_{j=1}^{n}|A_{j}|)-1 )$.
This gives us by induction that $|A_{n}|= t_{1}, |A_{n-1}|= t_{2}-t_{1}, \ldots, |A_{1}|= t_{n}-t_{n-1}$ and a quick calculation shows that the sum of all sets is exactly $1+\sum_{j=1}^{n}(t_{j}-t_{j-1})=t_{n}+1$. (where the $+1$ comes from the set $A_{\left\lceil\frac{n}{2}\right\rceil}$ and $t_{0}=0$.)