Maths Olympiad Prep

Library / /46 of 53

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it China

nn (n3n \ge 3) table tennis players have a round-robin tournament — each player will play all the others exactly once, and there is no draw game. Suppose, after the tournament, all the players can be arranged in a circle such that, for any three players AA, BB, CC, if AA, BB are adjacent, then at least one of them defeated CC. Please find all possible values of nn. (posed by Fu Yunhao)

Solution

We will prove that nn can be any odd number not less than 33.

Suppose n=2k+1n = 2k + 1, an odd number greater than 33, and nn players are represented by A1,A2,,A2k+1A_1, A_2, \dots, A_{2k+1}. Let us arrange the competition result as follows: AiA_i (1i2k+11 \le i \le 2k+1) defeated Ai+2,Ai+4,,Ai+2kA_{i+2}, A_{i+4}, \dots, A_{i+2k} (we stipulate that A2k+1+j=AjA_{2k+1+j} = A_j, j=1,2,,2k+1j = 1, 2, \dots, 2k+1) but lost to the other players. Then these players can be arranged in a circle in order A1,A2,,A2k+1,A1A_1, A_2, \dots, A_{2k+1}, A_1.

Now, given any three players AA, BB, CC with AA, BB being adjacent in the circle, we may assume that A=AiA = A_i, B=Ai+1B = A_{i+1}, C=Ai+rC = A_{i+r} (1i2k+11 \le i \le 2k+1, 2r2k2 \le r \le 2k). Then either rr or r1r-1 is an even number not less than 2k2k, which implies that at least one of the players AA, BB defeated CC.

On the other hand, suppose nn is an even number not less than 44, and the nn players can be arranged in a circle A1,A2,,An,A1A_1, A_2, \dots, A_n, A_1 that meets the required condition. We may assume that A1A_1 defeated A2A_2. According to the requirement, at least one of A2A_2, A3A_3 defeated A1A_1, and then A3A_3 defeated A1A_1; but at least one of A1A_1, A2A_2 defeated A3A_3, so A2A_2 defeated A3A_3, and so forth. We then get that, for any 1in1 \le i \le n, AiA_i defeated Ai+1A_{i+1} and lost to Ai1A_{i-1} (stipulate that An+1=A1A_{n+1} = A_1, A0=AnA_0 = A_n).

We now divide the players after AiA_i and before Ai1A_{i-1} into n22\frac{n-2}{2} pairs — each consists of two adjacent players. Then there is at least one player in each pair who defeated AiA_i, and that means, besides Ai1A_{i-1}, there are at least n22\frac{n-2}{2} players who defeated AiA_i. Then AiA_i lost at least n2\frac{n}{2} games. So nn players lost totally at least n22\frac{n^2}{2} games.

But the number of total games is Cn2=n(n1)2<n22C_n^2 = \frac{n(n-1)}{2} < \frac{n^2}{2}. This is a contradiction. Therefore, the possible values of nn are all the odd numbers not less than 33.

\boxed{}

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.