Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /111 of 120

Brazilian Mathematical Olympiad

Combinatorics Difficulty 6.8 National Olympiad Prove it Brazil

There are nn football teams in Tumbólia.
A championship is to be organized in which each team plays against every other exactly once. Every match takes place on Sundays and one team must not play more than once in the same day.
Find the least integer mm for which it's possible to set up a championship lasting mm Sundays.

Solution

First case: nn is even.
Let T1,T2,…,TnT_1, T_2, \dots, T_n be the teams. Each team shall play n−1n-1 times on at least n−1n-1 Sundays. Let us show that n−1n-1 Sundays are sufficient to set up the championship.

Teams TiT_i and TjT_j play on the dijd_{ij}-th Sunday. Define dijd_{ij} by the following rules:
dij={i+j(modn−1)if i,j≠n2i(modn−1)if i≠n and j=n2j(modn−1)if i=n and j≠n d_{ij} = \begin{cases} i+j \pmod{n-1} & \text{if } i, j \neq n \\ 2i \pmod{n-1} & \text{if } i \neq n \text{ and } j = n \\ 2j \pmod{n-1} & \text{if } i = n \text{ and } j \neq n \end{cases}
Let us show that dij=dikd_{ij} = d_{ik} implies j=kj = k. If i=ni = n, we have 2j≡2k(modn−1)⇔j≡k(modn−1)2j \equiv 2k \pmod{n-1} \Leftrightarrow j \equiv k \pmod{n-1}. Since j,k≤n−1j, k \le n-1, we must have j=kj = k. If i≠ni \ne n and j,k≠nj, k \ne n, i+j≡i+k(modn−1)⇔j≡k(modn−1)i+j \equiv i+k \pmod{n-1} \Leftrightarrow j \equiv k \pmod{n-1}, which implies j=kj = k. If i≠ni \ne n and j=nj = n and k≠nk \ne n, we have 2i≡i+k(modn−1)⇔i≡k(modn−1)2i \equiv i+k \pmod{n-1} \Leftrightarrow i \equiv k \pmod{n-1}, which implies i=ki = k, absurd. Hence dij=dik⇔j=kd_{ij} = d_{ik} \Leftrightarrow j = k.
Thus n−1n-1 Sundays are sufficient to set up the championship.

Second case: nn is odd.
Each team must play n−1n-1 times on at least n−1n-1 Sundays. However on each Sunday at least one team does not play. Hence m≥nm \ge n.
Let us prove that nn Sundays are sufficient. Let T0T_0 be a "dummy" team. If TiT_i plays against T0T_0 on a given Sunday, it means that TiT_i doesn't play on that Sunday. Thus we have n+1n+1 teams. As n+1n+1 is even, as shown above, we know that (n+1)−1=n(n+1)-1 = n Sundays are sufficient.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.