Maths Olympiad Prep

Library / /6 of 6

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 n1n-1 times on at least n1n-1 Sundays. Let us show that n1n-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(modn1)if i,jn2i(modn1)if in and j=n2j(modn1)if i=n and jn 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 2j2k(modn1)jk(modn1)2j \equiv 2k \pmod{n-1} \Leftrightarrow j \equiv k \pmod{n-1}. Since j,kn1j, k \le n-1, we must have j=kj = k. If ini \ne n and j,knj, k \ne n, i+ji+k(modn1)jk(modn1)i+j \equiv i+k \pmod{n-1} \Leftrightarrow j \equiv k \pmod{n-1}, which implies j=kj = k. If ini \ne n and j=nj = n and knk \ne n, we have 2ii+k(modn1)ik(modn1)2i \equiv i+k \pmod{n-1} \Leftrightarrow i \equiv k \pmod{n-1}, which implies i=ki = k, absurd. Hence dij=dikj=kd_{ij} = d_{ik} \Leftrightarrow j = k.
Thus n1n-1 Sundays are sufficient to set up the championship.

Second case: nn is odd.
Each team must play n1n-1 times on at least n1n-1 Sundays. However on each Sunday at least one team does not play. Hence mnm \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,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.