Number of Games in a Tournament

Problem: 1000 players compete in a tournament. In each round, players are matched with opponents, and the winner proceeds to the next round. If there are an odd number of players in a round, one player chosen at random sits out of that round. What is the total number of games are played in the tournament?

Solution: 999. Each player loses exactly one game, except for the winner of the tournament. Hence, in a tournament of n players, there will be n-1 games played. More formally, we have a bijection between the losers of the tournament and the games played, where each loser is paired with the game he lost. Since there are n-1 losers and one winner, there are n-1 games played.

This is a wonderful argument, particularly because it is entirely based on logic. Another attempt might be combinatorical or number-theoretical, counting the number of games in each round. While this would work nice for tournaments where there are 2^n players, here it flounders. This method works much more generally, and stands as a testament to the power of logic.

Advertisements

One thought on “Number of Games in a Tournament

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s