Maths Olympiad Prep

Track / Stage 4 / 330 of 340 #1070 of 2444

Problem 1070

AMC 12 late, AIME early
Combinatorics Difficulty 5.0 Prove it Spring Mathematical Tournament · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

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