Olympiad Maths Prep

Library / /23 of 30

Combinatorics Difficulty 6.7 National olympiad Prove it Belarus

There are three chess boards in a chess club, one of them is peaceful, the other one is fair, and the third board is strange. If two chess players use the peaceful board, then the result of their game is always a draw, if they use the fair board, then a stronger player wins, but if players use the strange board, then a stronger player loses.
Is it possible to organize the chess tournament between six chess players (none of them is equal to another in power) so that the following conditions hold: the tournament consists of five rounds, each round consists of three games and all these three chess boards are used, each participant plays exactly one game with every other participant, and the position of each player in the final table of the results of the tournament corresponds to the power of the player?
(A participant receives 1 point for a win, 1/2 point for a draw, and 0 point for a loss.)
(I. Bliznets)

Solution

We number chess players in accordance with their power: P1,P2,P3,P4,P5,P6P_1, P_2, P_3, P_4, P_5, P_6 (if the ii'th player is stronger than the jj'th one, then i<ji < j). Suppose, contrary to our claim, that the tournament can be organized. Let chess player PiP_i get aia_i points (i=1,,6i = 1, \dots, 6). By conditions, aiai+10.5a_i - a_{i+1} \ge 0.5 for i=1,,5i = 1, \dots, 5. In particular
aiai+3=(aiai+1)+(ai+1ai+2)+(ai+2ai+3)0.5+0.5+0.5=1.5.(1) a_i - a_{i+3} = (a_i - a_{i+1}) + (a_{i+1} - a_{i+2}) + (a_{i+2} - a_{i+3}) \ge 0.5 + 0.5 + 0.5 = 1.5. \quad (1)
Let A={P1,P2,P3}A = \{P_1, P_2, P_3\}, B={P4,P5,P6}B = \{P_4, P_5, P_6\}, SA=a1+a2+a3S_A = a_1 + a_2 + a_3, SB=a4+a5+a6S_B = a_4 + a_5 + a_6. It is easy to see that SA+SB=15S_A + S_B = 15. Moreover SASB4.5S_A - S_B \ge 4.5. Indeed
SASB=(a1+a2+a3)(a4+a5+a6)=(a1a4)+(a2a5)+(a3a6)1.5+1.5+1.5=4.5.(2) S_A - S_B = (a_1 + a_2 + a_3) - (a_4 + a_5 + a_6) = (a_1 - a_4) + (a_2 - a_5) + (a_3 - a_6) \ge 1.5 + 1.5 + 1.5 = 4.5. \quad (2)
Let SY(X)S_Y(X) denote the total number of points got by the chess players of group X in the games with the chess players of group Y (here X,Y{A,B}X, Y \in \{A, B\}).
It is evident that SA(A)=SB(B)=3S_A(A) = S_B(B) = 3. It follows that SB(A)SA(B)=(SA(A)+SB(A))(SA(B)+SB(B))=SASBS_B(A) - S_A(B) = (S_A(A) + S_B(A)) - (S_A(B) + S_B(B)) = S_A - S_B. The total number of the games between the players of A and B is equal to 33=93 \cdot 3 = 9, so 91=99 \cdot 1 = 9 points are distributed in these games. So for SASB4.5S_A - S_B \ge 4.5 it is necessary to have SB(A)7S_B(A) \ge 7. Otherwise, SB(A)6.5S_B(A) \le 6.5 gives SA(B)=9SB(A)2.5S_A(B) = 9 - S_B(A) \ge 2.5, which implies SASB6.52.5=4S_A - S_B \le 6.5 - 2.5 = 4, contrary to (2).
For SB(A)7S_B(A) \ge 7 it is necessary to use the fair board at least 5 times, otherwise, since only using the fair board gives 1 point to a stronger player, SB(A)41+50.5=6.5S_B(A) \le 4 \cdot 1 + 5 \cdot 0.5 = 6.5, which is impossible.
Since the fair board is used exactly 5 times, the players from A must use the peaceful board for the remaining 4=954 = 9-5 games with the players from B to obtain SB(A)7=5+40.5S_B(A) \ge 7 = 5+4 \cdot 0.5.
Therefore the peaceful board is used at most 1 time for the games between the players of the same group. It follows that a61+0.5=1.5a_6 \ge 1 + 0.5 = 1.5. Then
15=SA+SB=a6+a5+a4+a3+a2+a11.5+2+2.5+3+3.5+4=16.5, 15 = S_A + S_B = a_6 + a_5 + a_4 + a_3 + a_2 + a_1 \ge 1.5 + 2 + 2.5 + 3 + 3.5 + 4 = 16.5,
a contradiction. Hence it is impossible to organize the tournament satisfying the problem conditions.

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.