Maths Olympiad Prep

Library / /180 of 520

Combinatorics Difficulty 5.0 AIME, harder Find the answer

2.18 A football league consists of 18 teams playing a round-robin tournament, meaning each round the 18 teams are divided into 9 pairs, and each pair plays one match. In the next round, the teams are re-grouped to play again, for a total of 17 rounds, ensuring that each team plays against each of the other 17 teams exactly once. After playing nn rounds according to any feasible schedule, there always exist 4 teams that have played a total of only one match among themselves. Find the maximum possible value of nn.

A number or a short expression. Spacing and $ signs are ignored.

Solution

First, construct a tournament scheme: number the 18 teams sequentially as 1,2,,181, 2, \cdots, 18, and form two subsets according to odd and even numbers:
A={1,3,,17},B={2,4,,18}, A=\{1,3, \cdots, 17\}, B=\{2,4, \cdots, 18\},

Then, the teams (x,y)(x, y) for each match are assigned to rounds based on the remainder when x+yx+y is divided by 9. First, arrange 4 matches between teams of the same parity, then arrange one match for the "odd team out," requiring that in the rr-th round, each match's teams (x,y)(x, y) satisfy:
x+yr(mod9). x+y \equiv r(\bmod 9) .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.