The volleyball championship with $16$ teams was held in one round (each team played with each exactly one times, there are no draws in volleyball). It turned out that some two teams won the same number of matches. Prove there are the three teams that beat each other in a round robin (i.e. A beat B, B beat C, and C beat A).
Problem
Source: Moscow mathematic olympiad 2022, Day 2 P11.2
Tags: combinatorics
Sleepy_Head
30.09.2022 02:27
RagvaloD wrote: The volleyball championship with $16$ teams was held in one round (each team played with each exactly one times, there are no draws in volleyball). It turned out that some two teams won the same number of matches. Prove there are the three teams that beat each other in a round robin (i.e. A beat B, B beat C, and C beat A).
This problem appears to be a pigeonhole problem given the condition that two teams won the same number of matches and the condition we have been asked to prove. In that way, this problem is similar to 1964 IMO P4, which asks to prove that three people write to each other about the same subject. There is also a famous idea involving pigeonhole that states that in any group of 6 people, there is a group of 3 people such that each person is friends with the other two or each person is strangers with the other two. This problem may involve some of the same strategies as said examples.
R8kt
01.10.2022 11:29
If a tournament has a cycle, it has a triangle, and the only way a tournament on n vertices doesn’t have a cycle is if one person won n-1 matches, another won n-2 and so on. The problem condition doesn’t allow this type of graph.
AngleWatchers
01.10.2022 12:16
yay finally i can solve something here
Let the teams be $a_1,a_2,a_3,\dots,a_{16}$. WLOG, let $a_1$ and $a_2$ have both $k$ wins, where $k\le14$ and $a_1$ beat $a_2$. This means that $a_1$ beat exactly $k-1$ teams besides $a_2$ and $a_2$ beat exactly $k$ teams besides $a_1$. By using $PHP$, there's always at least a team that $a_2$ beat, but $a_1$ didn't, thus making a triangle connection where they beat each other.