Maths Olympiad Prep

Library / /28 of 32

Combinatorics Difficulty 6.9 National olympiad Prove it Netherlands

We consider sports tournaments with n4n \ge 4 participating teams and where every pair of teams plays against one another at most one time. We call such a tournament balanced if any four participating teams play exactly three matches between themselves. So, not all teams play against one another.
Determine the largest value of nn for which a balanced tournament with nn teams exists.

Solution

We will show that 55 is the largest value of nn for which a balanced tournament with nn teams exists. First we will show that in a balanced tournament with n5n \ge 5 teams, there are no three teams that all play against one another in the tournament.

Suppose towards a contradiction that we can find three teams in a balanced tournament that all play against each other, say teams AA, BB and CC. Because n5n \ge 5 there are two other teams, say DD and EE. Since AA, BB and CC already play three matches between them, there are no other matches between the quadruple AA, BB, CC and DD. In other words: DD does not play against AA, BB and CC. The same holds for team EE. If we now consider the quadruple AA, BB, DD and EE we see that there are at most two matches: AA against BB, and possibly DD against EE. This means that we have found four teams such that there are not exactly three matches between these four teams. This is a contradiction.

Now we will show that a balanced tournament is not possible with n6n \ge 6 teams. Suppose that n6n \ge 6 and, towards a contradiction, that a balanced tournament with nn teams exists. We look at the first six teams, say teams AA to FF. Suppose that AA plays against at most two of these teams, say at most against BB and CC but not against DD, EE and FF. Since three matches have to be played among the quadruple AA, DD, EE and FF, the teams DD, EE and FF all have to play against one another. This is in contradiction with our previous findings.

We conclude that AA has to play against at least three of the teams, for example BB, CC and DD. This gives three matches in the quadruple AA, BB, CC, DD, so BB, CC and DD do not play any matches between them. Because the quadruple BB, CC, DD, EE also has to play three matches, EE has to play against all of BB, CC and DD. But now we find a contradiction in the quadruple AA, BB, CC, EE: there are already four matches between these teams (AA against BB, AA against CC, BB against EE, and CC against EE). Therefore a balanced tournament with n6n \ge 6 does not exist.

To conclude, we will show that a balanced tournament with five teams exists.
To make such a tournament, imagine the teams are standing in a circle.
Two teams play against each other if they are standing next to each other in the circle. If we look at any quadruple of teams, we see there are exactly three pairs of teams standing next to each other in the circle. So the four teams plays three matches between them. We conclude that 55 is the largest value of nn for which a balanced tournament with nn teams exists. □

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.