Olympiad Maths Prep

Track / Stage 5 / 330 of 400 #930 of 2000

Problem 930

AIME late
Combinatorics Difficulty 5.8 Find the answer

Problem 11.5. In a chess tournament, a team of schoolchildren and a team of students, each consisting of 15 people, are competing against each other. During the tournament, each schoolchild must play against each student exactly once, and each person must play no more than one game per day. The number of games played on different days may vary.

At some point in the tournament, the organizer noticed that the schedule for the next day can be arranged in exactly 1 way with 15 games, and in NN ways with 1 game (the order of the games in the schedule does not matter, only who plays against whom). Find the maximum possible value of NN.

Official solution

Answer: 120.

Solution. Note that NN is the total number of games that remain to be played in the tournament.

Let's describe an example where N=120N=120. Number the students and schoolchildren from 1 to 15. Suppose the schoolchild with number kk needs to play with students numbered from 1 to kk. Then the total number of games remaining to be played is

1+2+3++15=120 1+2+3+\ldots+15=120

games. It is not hard to verify that there is exactly one way to schedule 15 games in one day (the first schoolchild must play with the first student, the second with the second, the third with the third, ..., the fifteenth with the fifteenth).

Now we will prove that N120N \leqslant 120. Without loss of generality, we will assume that the only way to play 15 games is when the first schoolchild plays with the first student, the second schoolchild with the second student, ..., the fifteenth schoolchild with the fifteenth student. These 15 pairs will be called direct, and pairs of players with different numbers will be called cross.

Note that we cannot have a situation where the kk-th schoolchild needs to play with the mm-th student, and the mm-th schoolchild needs to play with the kk-th student (otherwise, there is another way to play 15 games). Thus, for each pair of numbers kk and mm, no more than one cross game is scheduled. The total number of cross games is then no more than 15142=105\frac{15 \cdot 14}{2}=105. Adding the direct games, we get no more than 120.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.