Maths Olympiad Prep

Library / /1 of 5

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it European Girls' Mathematical Olympiad (EGMO)

Problem:

Let n1n \geq 1 be an integer and let t1<t2<<tnt_{1}<t_{2}<\ldots<t_{n} be positive integers. In a group of tn+1t_{n}+1 people, some games of chess are played. Two people can play each other at most once. Prove that it is possible for the following conditions to hold at the same time:

i) The number of games played by each person is one of t1,t2,,tnt_{1}, t_{2}, \ldots, t_{n},

ii) For every ii with 1in1 \leq i \leq n, there is someone who has played exactly tit_{i} games of chess.

Solutions — 4

Solution 1

Solution:

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

In the inductive step, suppose that T\mathcal{T} has n2n \geq 2 elements t1<t2<<tnt_{1}<t_{2}<\cdots<t_{n}. Consider the set
T={tntn1,tntn2,,tnt1}. \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 GG' of tnt1+1t_{n}-t_{1}+1 people that satisfies the conditions of the problem for TT'.

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

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

Solution 2

Solution:

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

In the inductive step, suppose that TT has n>2n>2 elements t1<<tnt_{1}<\ldots<t_{n}. Consider the set
T=(T{t1,tn})t1={tn1t1,tn2t1,,t2t1} \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 CC of tn1t1+1t_{n-1}-t_{1}+1 people that satisfies the conditions of the problem for TT'. Next add groups DD resp. EE of t1t_{1} resp. tntn1t_{n}-t_{n-1} people such that people from group DD played with everyone else whereas people from group EE only played with the people from group DD. Then the people from group CC played with tt other people if and only if they played with tt1t-t_{1} many people among CC, i.e. if and only if t{t2,,tn1}=T{t1,tn}t \in\{t_{2}, \ldots, t_{n-1}\}=\mathcal{T} \setminus\{t_{1}, t_{n}\}. People from group DD resp. EE played with tnt_{n} resp t1t_{1} people, which completes the proof.

Solution 3

Solution:

The proof proceeds by induction on tn|t_{n}|. If tn=1t_{n}=1 we have n=1n=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 tn>1t_{n}>1 we distinguish the two cases t1>1t_{1}>1 and t1=1t_{1}=1.

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

If t1=1t_{1}=1 there exists, by the induction hypothesis, a group BB of size tn1t_{n-1} that satisfies the conditions of the problem for t21,,tn11t_{2}-1, \ldots, t_{n-1}-1. Now add a new person PP and let him/her play with everyone from group BB and a group CC of size tntn1>0t_{n}-t_{n-1}>0 and let them play with PP. The new group will be of size tn1+1+(tntn1)+1=tn+1t_{n-1}+1+(t_{n}-t_{n-1})+1=t_{n}+1. Since person PP has played against everyone he will have played tnt_{n} games. The people in CC will have played 1=t11=t_{1} games. There exists a person in BB that has played tt games if and only if there exist a person in BB that has played t1t-1 games within BB, i.e. if and only if t{t2,,tn1}t \in\{t_{2}, \ldots, t_{n-1}\}. Hence the conditions of the problem are satisfied.

Solution 4

Solution:

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

Construction

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

Figure 1

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

Variant 1

Observation 1 Adding a person to a set AiA_{i} increases the number of games played in AjA_{j} for jni+1j \geq n-i+1, by exactly one.
Start with the construction above and then add t11t_{1}-1 people to group AnA_{n}, making the new set of games played equal to {t1,t1+1,,n+t11}\{t_{1}, t_{1}+1, \ldots, n+t_{1}-1\}. Then add t2t11t_{2}-t_{1}-1 to An1A_{n-1} to get set of games played to {t1,t2,t2+1,,n+t22}\{t_{1}, t_{2}, t_{2}+1, \ldots, n+t_{2}-2\} and repeat until we get to the set T\mathcal{T} adding a total of j=1ntjtj11=tnn\sum_{j=1}^{n} t_{j}-t_{j-1}-1=t_{n}-n people (let t0=0t_{0}=0 ), so we get tn+1t_{n}+1 people in the end.
Clearly we can start by adding vertices to A1A_{1} or any other set instead of AnA_{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 AiA_{i}'s all at once. We have by construction the number of games played in A1A_{1} is less than the number of games played in A2A_{2} etc. So we have that in the end we want the games played in AiA_{i} to be exactly tit_{i}.
So (t1,t2,t3,,tn)=!(An,An+An1,,(j=2nAj)1,(j=1nAj)1)(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 An=t1,An1=t2t1,,A1=tntn1|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+j=1n(tjtj1)=tn+11+\sum_{j=1}^{n}(t_{j}-t_{j-1})=t_{n}+1. (where the +1+1 comes from the set An2A_{\left\lceil\frac{n}{2}\right\rceil} and t0=0t_{0}=0.)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.