Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematik-Online lexicon:

Grand Slam

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview

The number of participants in a tennis tournament usually is a power of two: $ 2^n$ ($ n=7$ in a Grand Slam). The number of matches in a ''sudden death tournament" (knockout system) is $ 2^n-1$, which can be proved via Mathematical Induction:

Base step ($ n=1$):

With $ 2 = 2^1$ participants taking part in the tournament, the number of matches is $ 2^1-1 = 1$ . Thus the assertion holds for $ n=1$ .

Conclusion ($ n\to n+1$):

We assume that the assertion is true for $ 2^n$ participants (induction hypothesis).

Then $ 2^{n+1}$ participants can be divided into two groups of $ 2^n$ participants each. According to the induction hypothesis $ 2^n-1$ matches take place in each group, that is $ 2 \cdot (2^n-1)$ matches altogether. At last, the winners of each of the two groups then plays against the other. In total we get

$\displaystyle 2 \cdot (2^n-1) + 1 = 2^{n+1}-1 $

matches for $ 2^{n+1}$ participants.

In this example, the solution can be found faster with another argument: Since the tournament is a sudden death tournament, every player except the winner loses exactly one match. On the other hand, each match has exactly one loser. Thus there must be one match less than the number of participants.

This alternative proof can be applied to any number of participants (also when there are buys, for example). The proof shows that such tournaments with $ m$ participants always consist of $ m-1$ matches.

Obviously, induction is not always the best method of proof.

The case $ n=3$ is illustrated in the following chart, showing the $ 3$ final rounds of Wimbledon 1985, which was finally won by Boris Becker at the age of 17.

\includegraphics[width=.8\linewidth]{FigTennis}
(Authors: Höllig/Hörner/Kimmerle/Abele)

see also:

  automatisch erstellt am 11.  6. 2007