Olympiad Maths Prep

Library / /2 of 4

Combinatorics Difficulty 5.9 AIME, harder Prove it Greece

A company consisting of nn friends play a table game according to the following rules:
(a) At each round play exactly 3 players.
(b) The game stops after nn rounds.
(c) Each couple of players have played together at least at one round.
Determine the maximal possible value of nn.

Solution

Since in each round play exactly 3 players, the number of couples playing at each round is (32)=3\binom{3}{2} = 3. Therefore, at the end of the game after nn rounds, the total number of couples played the game will be 3n3n. According to the last rule:
(n2)3nn(n1)23nn123n7. \binom{n}{2} \le 3n \Leftrightarrow \frac{n(n-1)}{2} \le 3n \Leftrightarrow \frac{n-1}{2} \le 3 \Leftrightarrow n \le 7.
Next we will prove that the value n=7n=7 is possible. In fact, for n=7n=7 we have (72)=7!2!5!=672=21=37\binom{7}{2} = \frac{7!}{2!5!} = \frac{6 \cdot 7}{2} = 21 = 3 \cdot 7. If the friends are: AA, BB, Γ\Gamma, Δ\Delta, EE, ZZ, HH, then we can define the following triads (A,B,Γ)(A, B, \Gamma), (A,Δ,E)(A, \Delta, E), (A,Z,H)(A, Z, H), (B,Δ,H)(B, \Delta, H), (B,E,Z)(B, E, Z), (Γ,Δ,Z)(\Gamma, \Delta, Z), (Γ,E,H)(\Gamma, E, H).

Looking for a route rather than 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.