15th Chinese 2000 Problem A3 A doubles tournament is arranged as follows. Each player belongs to one or two doubles. Two doubles play at most one match against each other, but if two doubles share a player, then they do not compete against each other. Given a set {a 1 , a 2 , ... , a n } of distinct positive integers, what is the smallest number of players for which a tournament could be arranged such that (1) the number of matches played by each player is one of the a i , and (2) given any a i we can find at least one player who played (exactly) that number of matches. Solution
: 3k+3, where k = max a i /6. Solution by Abhishek Saha We show first that the number of players must be at least 3k+3. Some player A played in 6k matches. If A was in only one double, then that double played against 6k other doubles. Each player is in at most 2 doubles, so 6k doubles must include at least 6k different players. Hence the total number of players is at least 6k+1 > 3k+3. So suppose A was in two doubles. One of them must have played at least 3k other doubles. Thus there were at least 3k+3 players (A + his two partners + at least 3k opponents). Now we show that a tournament can be arranged with 3k+3 players. We show first that given n distinct positive integers b 1 , b 2 , ... , b n with max b i = k > 1, we can find a graph with k+1 points such that (1) at least one of the points has exactly b i edges (for each i), and (2) every point has b i edges for some i. We use induction on B = b 1 + b 2 + ... + b n . If B = 1, then n = 1, b 1 = 1 and k = 1. The graph with 2 points and 1 edge meets the conditions. So suppose the result is true for 1, 2, ... , B and we have b 1 + ... + b n = B+1. If all b i > 1, use induction to find a graph with k points for b 1 - 1, b 2 - 1, ... , b n - 1. Then take an additional point joined to each of the k points. If one of the b i is 1, then there is no loss of generality in assuming b n-1 = 1, b n = k. Suppose the largest of b 1 , b 2 , ... , b n-2 is b n-2 = h < k. Use induction fo find a graph with h points for b 1 - 1, b 2 - 1, ... , b n-2 - 1. Now add k - h points with no edges. Finally add one more point with edges to all k existing points. That gives a graph with b 1 , b 2 , ... , b n and completes the induction. So take b i = a i /6 and find the graph with k + 1 points. With each point P i of the graph associate the doubles A i B i , B i C i and C i A i . Now two doubles play if their associated points are joined. If a point of the graph has m edges, then a double at that point plays 3 games for each edge, but each player is in two doubles, so the player plays 6m games in total. 15th Chinese 2000 © John Scholes jscholes@kalva.demon.co.uk 22 July 2002