There are 15 teams joining a sports competition. All 15 teams must compete with each other once in a match of 2. At any time during the sports competition, is it true that we can always find at least 2 teams with the same number of matches they joined?
Bonus: Explain why.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let's say we halt the competition at an arbitrary point. Assume that no two teams have competed in the same number of matches.
The most matches a team can have played is 1 4 (once each against every other team); the least is 0 . There are exactly 1 5 integers in the list 0 , 1 , ⋯ , 1 4 ; so one team (call it T 0 ) must have played no matches, one team has played one match, etc, and one team, T 1 4 , must have played all 1 4 matches. But T 1 4 cannot have played T 0 ! Contradiction; so it is always possible to find two teams that have played the same number of matches.