Maths Olympiad Prep

Library / /4 of 14

Combinatorics Difficulty 5.0 AIME Prove it Bulgaria

In a tournament of beach volleyball with nn players and nn games any two players play in one and the same game at least one. Find the maximal value of nn.

Solution

The four players in a game form 6 pairs. Since any pair plays in at least one game, the number of all pairs (n2)=n(n1)2\binom{n}{2} = \frac{n(n-1)}{2} do not exceed 6 times the number of the games, i.e., 6n6n. Hence n(n1)26n\frac{n(n-1)}{2} \le 6n which is equivalent to n13n \le 13.

For n=13n = 13 let 1,2,,131, 2, \dots, 13 be the numbers of the players. A possible distribution with 13 games is the following: players i,i+2,i+3,i+7i, i+2, i+3, i+7 (modulo 13) play in game number ii, 1i131 \le i \le 13. It is easy to see that any two players play in one and the same game exactly once.

Hence the maximal value of nn equals 13.

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 and solution reproduced as published; topic and difficulty added by this site.