Maths Olympiad Prep

Library / /180 of 462

Combinatorics Difficulty 5.6 AIME, harder Prove it Ireland

The 2025 members of a football club run a tournament of “45-a-side” football matches, where each football match involves 90 people. After the tournament is concluded, it is noticed that no two football matches had four players in common. Prove that the number of football matches is less than 90.

Solution

Denote the players by P1,P2,,P2025P_1, P_2, \dots, P_{2025} and let the number of matches be NN. Also, denote the set of participants of match ii by Ti\mathcal{T}_i for each i=1,2,,Ni = 1, 2, \dots, N. We will count, in two different ways, the total number of triples (Pi,Tj,Tk)(P_i, \mathcal{T}_j, \mathcal{T}_k) such that PiP_i participates in match Tj\mathcal{T}_j as well in match Tk\mathcal{T}_k, i.e. PiTjP_i \in \mathcal{T}_j and PiTkP_i \in \mathcal{T}_k. Denote this total number of triples by TT.

First we count these triples by players. Suppose, for each 1i20251 \le i \le 2025, player PiP_i plays in RiR_i matches. We note that i=12025Ri=90N\sum_{i=1}^{2025} R_i = 90N. Then the number of triples (Pi,Tj,Tk)(P_i, \mathcal{T}_j, \mathcal{T}_k) with PiTjP_i \in \mathcal{T}_j and PiTkP_i \in \mathcal{T}_k, is

T=i=12025(Ri2)=12[i=12025Ri2i=12025Ri]12[(i=12025Ri)22025i=12025Ri]=12[(90N)2202590N]=2N245N,\begin{align} T &= \sum_{i=1}^{2025} \binom{R_i}{2} = \frac{1}{2} \left[ \sum_{i=1}^{2025} R_i^2 - \sum_{i=1}^{2025} R_i \right] \\ &\ge \frac{1}{2} \left[ \frac{\left(\sum_{i=1}^{2025} R_i\right)^2}{2025} - \sum_{i=1}^{2025} R_i \right] = \frac{1}{2} \left[ \frac{(90N)^2}{2025} - 90N \right] \\ &= 2N^2 - 45N, \tag{28} \end{align}

where in the second line we have used the Cauchy-Schwarz inequality.

Next, we give an upper bound for the number of these triples by considering pairs of matches. We know that no pair of matches has more than 3 players in common, so

T3(N2)=3N(N1)2.(29) T \le 3 \binom{N}{2} = \frac{3N(N-1)}{2}. \tag{29}

Combining (28) and (29) yields

2N245N3N(N1)2 2N^2 - 45N \leq \frac{3N(N-1)}{2}

which, upon simplifying, gives N87N \leq 87.

Therefore, the number of football matches is less than 9090.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.