Maths Olympiad Prep

Library / /80 of 104

Combinatorics Difficulty 6.5 National Olympiad Prove it Bulgaria

Problem:

In an internet chess tournament 2005 chess players took part and everyone played one game against any other. After the tournament it appeared that for every two players AA and BB who had drawn their game every other player had lost his game with AA or with BB. Prove that if there were at least two draws in the tournament then the players can be ordered in such a way that everyone has won his game with the next one in the sequence.
Emil Kolev

Solution

Solution:

Note that a chess player could not have more than one draw. Indeed, if AA had draws with BB and CC, then the condition for AA and BB implies that BB defeated CC and the same condition for AA and CC implies that CC defeated BB, a contradiction.

Let A1,A2,,AkA_{1}, A_{2}, \ldots, A_{k} be the longest sequence such that each chess player has defeated the next one, i.e. AiA_{i} has defeated Ai+1A_{i+1} for i=1,2,,k1i=1,2, \ldots, k-1. If k=2005k=2005, then we have the required sequence. Assume that k<2005k<2005 and consider a chess player BB who is not amongst A1,A2,,AkA_{1}, A_{2}, \ldots, A_{k}.

If BB has defeated A1A_{1} then the sequence B,A1,A2,,AkB, A_{1}, A_{2}, \ldots, A_{k} of length k+1k+1 has the above property, which is impossible.

If A1A_{1} has defeated BB, then BB and A2A_{2} had not draw because A1A_{1} has defeated both. If BB has defeated A2A_{2} then the sequence A1,B,A2,,AkA_{1}, B, A_{2}, \ldots, A_{k} of length k+1k+1 has the above property, a contradiction. Therefore A2A_{2} has defeated BB. We see analogously that all players A3,A4,,AkA_{3}, A_{4}, \ldots, A_{k} have defeated BB. Then we obtain again a contradiction by considering the sequence A1,A2,,Ak,BA_{1}, A_{2}, \ldots, A_{k}, B of length k+1k+1.

The above argument shows that outside the sequence A1,A2,,AkA_{1}, A_{2}, \ldots, A_{k} there is only one chess player BB, and A1A_{1} and BB made a draw. Then this is the only draw of BB. If A2A_{2} has defeated BB, then we obtain as above that BB has lost from AiA_{i} for i=3,4,,ki=3,4, \ldots, k and we have again sequence A1,A2,,Ak,BA_{1}, A_{2}, \ldots, A_{k}, B of length k+1k+1. Therefore A2A_{2} has lost from BB and the same holds for Ai,i=3,,kA_{i}, i=3, \ldots, k.

On the other hand, there is at least one more draw, for example between AiA_{i} and AjA_{j}. But AiA_{i} and AjA_{j} have lost from BB, which is a contradiction.

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.