Teams In a Tournament

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

1. I. F. Sharygin, Mathematical Mosaic, Mir, 2002, problem 65.1 (in Russian)

Related material Read more...
	Pigeonhole Principle and Extensions
	Twenty five boys and twenty five girls
	Pigeonhole in Chess Training
	Married Couples at a Party
	Jumping Isn't Everything
	Zeros and Nines
	Divisibility of a Repunit
	Pigeonhole in Clubs

|Contact| |Front page| |Contents| |Up| |Store|