Source code online books for professionals by professionals

Figure 3-1.  A complete graph, illustrating a round-robin tournament, or the handshake problem

---

ChapTer 3 
■
 CounTIng 101
47
The Hare and the Tortoise
Let’s say our knights are 100 in number and that the tournament staff are still a bit tired from last year’s round 
robin. That’s quite understandable, as there would have been 4,950 matches. They decide to introduce the (more 
efficient) knockout system and want to know how many matches they’ll need. The solution can be a bit tricky 
to find ... or blindingly obvious, depending on how you look at it. Let’s look at it from the slightly tricky angle 
first. In the first round, all the knights are paired, so we have n/2 matches. Only half of them go on to the second 
round, so there we have n/4 matches. We keep on halving until the last match, giving us the sum n/2 + n/4 + n/8 
+ ... + 1, or, equivalently, 1 + 2 + 4 + ... + n/2. As you’ll see later, this sum has numerous applications, but what is 
the answer?
Now comes the blindingly obvious part: In each match, one knight is knocked out. All except the winner are 
knocked out (and they’re knocked out only once), so we need n–1 matches to leave only one man (or woman) 
standing. The tournament structure is illustrated as a rooted tree in Figure 
3-2
, where each leaf is a knight and each 
internal node represents a match. In other words:
2
1
0
1
i
i
h
n
=
-
å
= -
n−1
Figure 3-2.  A perfectly balanced rooted, binary tree with n leaves and n–1 internal nodes (root highlighted). The tree 
may be undirected, but the edges can be thought of as implicitly pointing downward, as shown
The upper limit, h–1, is the number of rounds, or h the height of the binary tree, so 2
h
 = n. Couched in this 
concrete setting, the result may not seem all that strange, but it sort of is, really. In a way, it forms the basis for the 
myth that there are more people alive than all those who have ever died. Even though the myth is wrong, it’s not that 
far-fetched! The growth of the human population is roughly exponential and currently doubles about every 50 years. 
Let’s say we had a fixed doubling time throughout history; this is not really true,
2
 but play along. Or, to simplify things 
even further, assume that each generation is twice as populous as the one before.
3
 Then, if the current generation 
consists of n individuals, the sum of all generations past will, as we have seen, be only n–1 (and, of course, some of 
them would still be alive).
2
http://prb.org/Articles/2002/HowManyPeoplehaveEverLivedonEarth.aspx
.
3
If this were true, the human population would have consisted of one man and one woman about 32 generations ago ... but,  
as I said, play along.

---

ChapTer 3 
■
 CounTIng 101
48