Maths Olympiad Prep

Library / /8 of 8

Combinatorics Difficulty 8.8 Shortlist Prove it Netherlands

A group of 4050 friends is playing a video game tournament. There are 2025 computers labelled a1,,a2025a_1, \dots, a_{2025} in one room and 2025 computers labelled b1,,b2025b_1, \dots, b_{2025} in another room at the tournament. The player on computer aia_i always plays against the players bi,bi+2,bi+3b_i, b_{i+2}, b_{i+3} and bi+4b_{i+4} (in particular, not against bi+1b_{i+1}), where the numbers of the computers are considered modulo 2025. After the first round, all players choose a computer within their room for the second round. Afterwards, they note that everyone has the same opponents in the second round as in the first round.
Prove that if someone chose the same computer in both rounds, then everyone chose the same computer in both rounds.

Solution

For the opponent computers of aia_i, we look at the aja_j they are playing against, see the following table.

bi:b_i:
| ai4a_{i-4} | ai3a_{i-3} | ai2a_{i-2} | aia_i |
|---|---|---|---|

bi+2:b_{i+2}:
| ai2a_{i-2} | ai1a_{i-1} | aia_i | ai+2a_{i+2} |
|---|---|---|---|

bi+3:b_{i+3}:
| ai1a_{i-1} | aia_i | ai+1a_{i+1} | ai+3a_{i+3} |
|---|---|---|---|

bi+4:b_{i+4}:
| aia_i | ai+1a_{i+1} | ai+2a_{i+2} | ai+4a_{i+4} |
|---|---|---|---|

Note that computers ai2a_{i-2}, ai1a_{i-1}, ai+1a_{i+1} and ai+2a_{i+2} each have two common opponent computers with aia_i. Furthermore, ai4a_{i-4}, ai3a_{i-3}, ai+3a_{i+3} and ai+4a_{i+4} each have one common adversary computer with aia_i. Only for the first two, ai4a_{i-4} and ai3a_{i-3}, the common opponent with aia_i is the same, namely bib_i.

Figure 1

Now suppose one player chose the same computer for the second round, say the player on a2025a_{2025}. We will now prove by induction that all players on aia_i and bib_i have chosen the same computer for the second round.

Per the induction hypothesis, suppose that the player on a certain computer aia_i is the same in both rounds. Since everyone has the same opponents in both rounds, the players who were on ai4a_{i-4} and ai3a_{i-3} again each have the same common co-player in the game with aia_i, namely the player who was on bib_i. This means that the player on bib_i also chose the same computer. Now we note that only the player who was on ai2a_{i-2} has a second common opponent with aia_i in addition to bib_i. So also on ai2a_{i-2}, the same player chose the same computer again.

Since 2025 is odd, it now follows with induction that everyone has played on the same computer, as soon as any one player has played on the same computer. \square

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.