Browse · MathNet
PrintSAUDI ARABIAN MATHEMATICAL COMPETITIONS
Saudi Arabia counting and probability
Problem
There are totally 16 teams participating in a football tournament; each team playing with every other exactly 1 time. In each match, the winner gains 3 points, the loser gains 0 point and each team gains 1 point for the tie match. Suppose that at the end of the tournament, each team gains the same number of points. Prove that there are at least 4 teams that have the same number of winning matches, the same number of losing matches and the same number of tie matches.
Solution
First, we can see that if a team got win matches, lose matches and tie matches then they got points and . We call two teams having the same number of win matches, lose matches and tie matches as "relate".
Denote the number of win matches, lose matches and tie matches of two teams by respectively then then the difference between the tie matches is And two teams are relate if and only if they have the same number of tie matches.
The number of their tie matches lies between and and all are congruent modulo . So we can divide these teams into some groups by the number of tie matches (the teams in a group have the same number of tie matches). Hence, by the Pigeonhole principle, the number of groups cannot exceed .
If there are some groups with greater than or equal to 4 members, i.e., 4 teams, then we are done.
Otherwise, each group contains 3 members or fewer. Then the number of groups must be 6, if not, the number of teams is not greater than 15, which is a contradiction.
But the only way to obtain 6 groups like that is the number of tie matches of 16 teams are . It means there are some teams that have all matches as ties and there are also some teams that have all matches not as ties, which is a contradiction.
Hence, there are some groups with at least 4 members.
Denote the number of win matches, lose matches and tie matches of two teams by respectively then then the difference between the tie matches is And two teams are relate if and only if they have the same number of tie matches.
The number of their tie matches lies between and and all are congruent modulo . So we can divide these teams into some groups by the number of tie matches (the teams in a group have the same number of tie matches). Hence, by the Pigeonhole principle, the number of groups cannot exceed .
If there are some groups with greater than or equal to 4 members, i.e., 4 teams, then we are done.
Otherwise, each group contains 3 members or fewer. Then the number of groups must be 6, if not, the number of teams is not greater than 15, which is a contradiction.
But the only way to obtain 6 groups like that is the number of tie matches of 16 teams are . It means there are some teams that have all matches as ties and there are also some teams that have all matches not as ties, which is a contradiction.
Hence, there are some groups with at least 4 members.
Techniques
Pigeonhole principleModular Arithmetic