17th Chinese 2002 Problem A3 18 people play in a tournament of 17 rounds. There are 9 games in each round and each person plays in one game in each round. Each person plays every other person just once in the tournament. What is the largest n such that however the tournament is arranged we can find 4 people amongst whom only one game has been played by the end of round n?
? n must be at least 7 Solution Many thanks to Aragorn for showing that n=7 works Now consider n = 7. Let S be the largest set of players none of whom have played each other and let S' be the set of the remaining players. Take A in S' who has played as few players in S as possible. Suppose |S| = m, so that |S'| = 18-m. We show that A has played at most m-2 members of S. Suppose not. Each player has played 7 games, and for members of S all these have been with members of S', so there have been 7m games between members of S and members of S'. If every member of S' has played m-1 or more members of S, then there have been at least (18 - m)(m - 1) games between members of S and members of S', so (18 - m)(m - 1) ≤ 7m, or m 2 - 12m + 18 ≥ 0, so m  10. Clearly m is not less than 2 (since there are certainly two players who have not played each other). If m > 10, then since A has played only 7 games, he has played less than m-2 members of S'. Thus we can find B and C in S, such that A has not played B or C. Since A is not in S and S is maximal, there must be D in S who has played A. Now A, B, C, D is the required set of 4 people amongst whom only one game has been played (A - D). To show that n=7 is best possible we have to exhibit a particular tournament such that given any 4 people, either 0 or ≥ 2 games have been played between them after 8 rounds. I cannot see how to do this at the moment. Note that it is certainly not true for all tournaments. It is not hard to construct a tournament which has 4 people with only 1 game between them after 13 rounds. 17th Chinese 2002 © John Scholes jscholes@kalva.demon.co.uk 4 March 2003 Last corrected/updated 28 Nov 03