digraph as a diagram of information flow.) In the
example above, team D is a source, and team B is a
sink. It is impossible for a tournament to possess two
different sources or two different sinks. A tournament
need not possess either a source or a sink.
Every tournament possesses a HAMILTONIAN PATH.
This means that it is possible to find a path through the
diagram of a complete digraph that starts at one vertex
and follows edges in directions that respect the arrows
to visit each and every other vertex exactly once. For
example, in the diagram above, the journey D → A →
C → B represents a Hamiltonian path. Alternatively, a
Hamiltonian path can be interpreted simply as a list of
all the teams that played arranged in an order so that
the first team on the list beat the second, the second
team on the list beat the third, and so forth. The following example illustrates a general method for constructing such a list (or, equivalently, a Hamiltonian
path) for any tournament.
Consider the following table outlining the
results of a tournament with five teams, A, B,
C, D, and E:
and consider the teams one at a time in order
to create an appropriate list. First write A.
Now if team B beat A, then it is permissible to
write B to the left of A. This is not the case,
however, and so B should be written to the
right of A. Our list, so far, appears: A B.
Now consider team C and ask, “Did C
beat A?” As the answer is no, we are not permitted to write C to the immediate left of A.
Did C beat B? Yes. Thus we are permitted to
write C to the immediate left of B. Our list
thus far reads: A C B. (We have that A beat C,
and C beat B.)
Now consider team D, and look for the
first team on the partially constructed list that
D beat. This is team A. This leads to the new
list: D A C B.
Finally consider team E. The first team on this
partially constructed list that E beat is C. This
allows us to place E between A and C to produce the complete list: D A E C B. Notice that
it does indeed have the property that each team
on the list beat the one succeeding it. This list
represents a Hamiltonian circuit in the appropriate digraph.
The total number of games played in a tournament
with N players is given by the formula:
(Each of the N teams plays N – 1 games, but this double counts the total number of games played.) This is
the (N – 1)th triangular FIGURATE NUMBER.
If N is odd, it is always possible to construct an
example of a tournament among N teams in which
each team has the same number of wins. This feat cannot be accomplished if N is even. (If each team has w
wins, then N × w represents the total number of games
played. Consequently, we must have
. This
is an invalid formula if N is even.)
tower of Hanoi (towers of Hanoi, tower of Brahma)
Consider three poles and a collection of differently
sized discs all placed initially on one pole in order of
size, largest at the bottom to the smallest at the top. An
ancient challenge demands that all the discs be transferred to a different pole in such a way that:
1. Only one disc is ever moved at a time.
2. No disc ever sits upon another disc of a smaller size.
An eight-disc version of this puzzle was patented
and sold as a toy by Edouard Lucas in 1883. He called
the puzzle the Tower of Hanoi and wrote that the game
was based on a “tower of Brahma” in which priests
were given the challenge of moving 64 discs from one
pole to another under the same restrictions, moving
just one disc a day. The legend claimed that the world
would end on the day the task is completed.
A puzzle containing just one or two discs is easily
solved. If one knows a method for solving the puzzle
with N discs, then the solution to the (N + 1)-disc version follows readily: transfer the top N discs to one
pole via the known method, move the large (N + 1)th
disc to the empty pole, and transfer the N discs to the
pole containing the large disc. If T(N) denotes the numw
N
=
− 1
2
N N
(
)
− 1
2
A beat B
Cbeat B
Cbeat D
Dbeat E
A beat C
Bbeat D
Ebeat C
D beat A
Bbeat E
A beat E
502 tower of Hanoi
example above, team D is a source, and team B is a
sink. It is impossible for a tournament to possess two
different sources or two different sinks. A tournament
need not possess either a source or a sink.
Every tournament possesses a HAMILTONIAN PATH.
This means that it is possible to find a path through the
diagram of a complete digraph that starts at one vertex
and follows edges in directions that respect the arrows
to visit each and every other vertex exactly once. For
example, in the diagram above, the journey D → A →
C → B represents a Hamiltonian path. Alternatively, a
Hamiltonian path can be interpreted simply as a list of
all the teams that played arranged in an order so that
the first team on the list beat the second, the second
team on the list beat the third, and so forth. The following example illustrates a general method for constructing such a list (or, equivalently, a Hamiltonian
path) for any tournament.
Consider the following table outlining the
results of a tournament with five teams, A, B,
C, D, and E:
and consider the teams one at a time in order
to create an appropriate list. First write A.
Now if team B beat A, then it is permissible to
write B to the left of A. This is not the case,
however, and so B should be written to the
right of A. Our list, so far, appears: A B.
Now consider team C and ask, “Did C
beat A?” As the answer is no, we are not permitted to write C to the immediate left of A.
Did C beat B? Yes. Thus we are permitted to
write C to the immediate left of B. Our list
thus far reads: A C B. (We have that A beat C,
and C beat B.)
Now consider team D, and look for the
first team on the partially constructed list that
D beat. This is team A. This leads to the new
list: D A C B.
Finally consider team E. The first team on this
partially constructed list that E beat is C. This
allows us to place E between A and C to produce the complete list: D A E C B. Notice that
it does indeed have the property that each team
on the list beat the one succeeding it. This list
represents a Hamiltonian circuit in the appropriate digraph.
The total number of games played in a tournament
with N players is given by the formula:
(Each of the N teams plays N – 1 games, but this double counts the total number of games played.) This is
the (N – 1)th triangular FIGURATE NUMBER.
If N is odd, it is always possible to construct an
example of a tournament among N teams in which
each team has the same number of wins. This feat cannot be accomplished if N is even. (If each team has w
wins, then N × w represents the total number of games
played. Consequently, we must have
. This
is an invalid formula if N is even.)
tower of Hanoi (towers of Hanoi, tower of Brahma)
Consider three poles and a collection of differently
sized discs all placed initially on one pole in order of
size, largest at the bottom to the smallest at the top. An
ancient challenge demands that all the discs be transferred to a different pole in such a way that:
1. Only one disc is ever moved at a time.
2. No disc ever sits upon another disc of a smaller size.
An eight-disc version of this puzzle was patented
and sold as a toy by Edouard Lucas in 1883. He called
the puzzle the Tower of Hanoi and wrote that the game
was based on a “tower of Brahma” in which priests
were given the challenge of moving 64 discs from one
pole to another under the same restrictions, moving
just one disc a day. The legend claimed that the world
would end on the day the task is completed.
A puzzle containing just one or two discs is easily
solved. If one knows a method for solving the puzzle
with N discs, then the solution to the (N + 1)-disc version follows readily: transfer the top N discs to one
pole via the known method, move the large (N + 1)th
disc to the empty pole, and transfer the N discs to the
pole containing the large disc. If T(N) denotes the numw
N
=
− 1
2
N N
(
)
− 1
2
A beat B
Cbeat B
Cbeat D
Dbeat E
A beat C
Bbeat D
Ebeat C
D beat A
Bbeat E
A beat E
502 tower of Hanoi