Lining Up Your Ducks Is More Difficult Than It Appears

The Mathematical Diary of 1825

Math Chat is certainly not the first mathematics column, even in the United States. Don Beaver reports that in 1825 R. Adrain launched a periodical called The Mathematical Diary in New York, which included challenge questions and answers.

Here is the very first challenge question, submitted by Charles Vyse.

"New" challenge (1825)

"Ten pounds [sterling] a quarter are allowed to five auditors, A, B, C, D, E, of a Fire Office. They are required to attend seven times in the quarter, and the absentees' shares are to be divided equally among such as attend. Now A and B never fail to attend, C and D are each absent twice, and E is absent only once: What is each auditor's share of the given sum?"

Friday the 13th (Victor Hill)

February and March 1998 provide two consecutive months each with a Friday the 13th. Amazingly, the 13th of the month is slightly more likely to fall on Friday than on any other day. This is just an accident of our calendar. In every 400-year cycle, the 13th of a month falls on Friday 688 times, on Sunday and Wednesday 687 times, on Monday and Tuesday 685 times, and on Thursday and Saturday 684 times.

Old weighing challenge

(Joe Shipman)

A balance scale tells which of two objects is heavier. How many weighings does it take to put three objects in order from heaviest to lightest? What about four objects? What about five objects?

Answer

Michael Marcotty rightly prescribes three weighings for three objects, five weighings for four objects, and seven weighings for five objects.

Three objects indeed can require as many as three weighings. After one weighing you might know that A is heavier than B, but if C is in between, you still have to compare it to both A and B to find out.

Four objects can require as many as five weighings. After two weighings you might know that A is heavier than B and that C is heavier than D. A third weighing might tell you, for example, that A is heavier than C. Now it could take two more weighings to find out that B is between C and D.

Five objects can require as many as seven weighings, and you have to be pretty clever to organize a strategy so that seven always suffice.

A computer needs some such strategy to alphabetize lists for example. Better strategies can save the country billions of dollars. This is all part of the mathematical theory of "sorting."

You can prove something about how many weighings are required. For example, there have to be enough weighings so the number of possible outcomes can cover all possible orderings. (Mathematically you would say: 2w n!)

This formula gives the exact answer for fewer than 12 objects. But it turns out that for 12 objects you can't do as well as you might think from the formula. In general, no one has been able to decide what the best strategy is.

* Send answers and new questions to:

Math Chat

Fine Hall

Washington Road

Princeton, NJ 08540

or by e-mail to:

fmorgan@princeton.edu