Maths Olympiad Prep

Library / /102 of 155

Combinatorics Difficulty 6.4 National olympiad Prove it Saudi Arabia

There are totally 1616 teams participating in a football tournament; each team playing with every other exactly 11 time. In each match, the winner gains 33 points, the loser gains 00 point and each team gains 11 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 44 teams that have the same number of winning matches, the same number of losing matches and the same number of tie matches.

Solutions — 2

Solution 1

See the solution to Problem 1 in the test of level 4. \square

Solution 2

First, we can see that if a team got xx win matches, yy lose matches and zz tie matches then they got 3x+z3x + z points and x+y+z=15x + y + z = 15. 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 A,BA, B by (x1,y1,z1),(x2,y2,z2)(x_1, y_1, z_1), (x_2, y_2, z_2) respectively then
3x1+z1=3x2+z2, 3x_1 + z_1 = 3x_2 + z_2,
then the difference between the tie matches is
z1z2=3x1x2 which is divisible by 3. |z_1 - z_2| = 3|x_1 - x_2| \text{ which is divisible by } 3.
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 00 and 1515 and all are congruent modulo 33. 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 153=6\left\lceil \frac{15}{3} \right\rceil = 6.

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 0,3,6,9,12,150, 3, 6, 9, 12, 15. 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. \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 and solution reproduced as published; topic and difficulty added by this site.