Illinois, achieved the maximum (20 dictionary
words), with:
SNAP
AERA
RAI L
TRAP
“Tras”is the plural of “tra,” a Malaysian coin.
7.
Five objects can be ranked according to weight
with no more than seven weighings on a bal-
ance scale:
1. Weigh A against B. Assume that B is
heavier.
2. Weigh C against D. Assume that D is
heavier.
3. Weigh B against D. Assume that D is
heavier. We now have ranked three objects:
D > B > A.
4. Weigh E against B.
5. If E is heavier than B, we now weigh it
against D. If E is lighter than B, we weigh it
against A. In either case E is brought into the
series so that we obtain a rank order of four
objects. Assume that the order is D> B > E >
A. We already know (from step 2) how the
remaining object C compares with D. Therefore
we have only to find C’s place with respect to
the rank order of the other three. This can
always be done in two weighings. In this case:
6. Weigh C against E.
7. If C is heavier than E, weigh it against B.
If C is lighter than E, weigh it against A.
The general problem of ranking n weights
with a minimum number of weighings (or n
tournament players with a minimum number of
no-draw two-person contests) was first pro-
posed by Hugo Steinhaus. He discusses it
briefly in the 1950 edition of Mathematical
Snapshots and includes it as Problem 52 (with n
= 5) in One Hundred Problems in Elementary
Mathematics (New York: Basic Books, 1964). In
the latest revision of Mathematical Snapshots
(New York: Oxford University Press, 1968),
Steinhaus gives a formula that provides correct
answers through n = 11. (For 1 through 11 the
minimum number of weighings are 0, 1, 3, 5, 7,
10, 13, 16, 19, 22, 26.) The formula predicts 29
weighings for 12 objects, but it has been proved
that the minimum number is 30.
The general problem is discussed by Lester
R. Ford and Selmer M. Johnson, both of the
Rand Corporation, in “A Tournament
Problem,” in The American Mathematical Monthly;
May, 1959. For a more recent discussion of this
and closely related problems, see Section 5.3.1
of Donald Knuth’s Sorting and Searching
(Reading, Mass.: Addison-Wesley, 1971) or suc-
cessor editions.
8.
Answers to the five queen’s-tour problems are
shown in Figure 92. In the fourth and fifth
problems there are solutions other than those
shown, but none in fewer moves.
Mathematical Games
124