Teams In a Tournament

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

  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|

    Copyright © 1996-2018 Alexander Bogomolny

    71493462