Abeat BCbeat BCbeat DDbeat E

Abeat CBbeat DEbeat C

Dbeat ABbeat E

Abeat E

502 tower of Hanoi

digraph as a diagram of information flow.) In the

example above, team Dis a source, and team Bis 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 H

AMILTONIAN 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→Brepresents 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 fol-

lowing example illustrates a general method for con-

structing 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 Bbeat A, then it is permissible to

write B to the left of A. This is not the case,

however, and so Bshould be written to the

right of A. Our list, so far, appears: A B.

Now consider team Cand ask, “Did C

beat A?” As the answer is no, we are not per-

mitted to write Cto the immediate left of A.

Did Cbeat B? Yes. Thus we are permitted to

write Cto the immediate left of B. Our list

thus far reads: A C B. (We have that Abeat C,

and Cbeat B.)

Now consider team D, and look for the

first team on the partially constructed list that

Dbeat. 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 Ebeat is C. This

allows us to place E between Aand Cto pro-

duce 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 appro-

priate digraph.

The total number of games played in a tournament

with Nplayers is given by the formula:

(Each of the Nteams plays N– 1 games, but this dou-

ble counts the total number of games played.) This is

the (N – 1)th triangular

FIGURATE NUMBER

.

If Nis odd, it is always possible to construct an

example of a tournament among Nteams in which

each team has the same number of wins. This feat can-

not be accomplished if Nis even. (If each team has w

wins, then N×wrepresents the total number of games

played. Consequently, we must have . This

is an invalid formula if Nis 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 trans-

ferred 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 Ndiscs, then the solution to the (N+ 1)-disc ver-

sion follows readily: transfer the top Ndiscs to one

pole via the known method, move the large (N+ 1)th

disc to the empty pole, and transfer the Ndiscs to the

pole containing the large disc. If T(N) denotes the num-