
| |
Teams In a Tournament: in a tournament where each team meets every other team once, there are always two teams that played the same number of games
|

At the beginning, all the teams played exactly zero games. Let there be N teams. In the course of the tournament, each team will play N - 1 games. So, at any moment, the number of games played by any team may range from 0 to N - 1 (inclusive). If there are two teams that did not played yet, the problem is sovled as these two teams, having played 0 games each, satisfy the problem requirement. If all teams played at least 1 game, there are N teams that played between 1 and N - 1 games (inclusive), and the pigeonhole principle works. If there is exactly one team that did not play yet, the problem reduces to the tournament of N - 1 teams, each having played at least one game. The number of games for each of the remaing N - 1 teams ranges from 1 through N - 2 (inclusive) and, hence, there is a pair of teams that played so far exactly the same number of games.
Reference
- I. F. Sharygin, Mathematical Mosaic, Mir, 2002, problem 65.1 (in Russian)

Copyright © 1996-2010 Alexander Bogomolny
|