The King Was in His Counting House...

Today with its final column, Math Chat thanks all its readers and hopes they continue to find enjoyment in mathematics and in every department of life.

Old gold challenge (John Dippel)

An ancient king requires that each of his 10 chieftains pay him tribute of 2,000 10-gram gold coins. He learns that one of them plans to substitute 9-gram coins, but he does not know which one. He has an accurate scale that reads out exact weight. How many weighings does he need to identify the cheater? What if there may be any number of cheaters?

Answer (James Fahs, Steve Jabloner, Ken Johnson, Sigmund Pfeiffer, Sam Ragucci, Samuel Root, Dave Rossum, Mike Seery, Walter Wright, Aubrey Dunne)

A single cheater can be identified in one weighing. The king takes one coin from the first chieftain, two from the second, three from the third, and so on, finally 10 from the 10th, and weighs them all at once. If the total is one gram short, the first chieftain is the cheater. If the total is two grams short, the second chieftain is the cheater, and so on.

Any number of cheaters also can be identified in one weighing! The king takes one coin from the first chieftain, two from the second, four from the third, eight from the fourth, and so on, doubling each time, finally 1,024 coins from the 10th.

If the total is 1 gram short, the first chieftain is the cheater. If the total is 2 grams short, the second chieftain is the cheater. If the total is 3 grams short, the first and second chieftains are cheaters. If the total is 4 grams short, the third chieftain is the cheater. If 5, the first and third; if 6, the second and third; if 7, the first, second, and third; if 8, the fourth; and so on.

If the king uses base 2 number symbols instead of our more familiar base 10, it becomes very easy to tell who the cheaters are. In base 10, a number like 3,579 (made up of digits less than 10) means 9 + 7 x 10 + 5 x 100 + 3 x 1,000, all in terms of powers of 10 (10, 100, 1,000, etc.). A base-2 number uses only digits less than 2. The base-2 number 110 for example means 0 + 1 x 2 + 1 x 4 = 6. If the king finds the total is 6 grams short, he writes 6 as 110 base 2, and then reading from right to left, seeing first a 0, second a 1, and third a 1, can conclude that the second and third chieftains are the cheaters.

Mike Seery reports, "This problem appeared on a 'Columbo' episode in the '70s."

Alone in the universe?

Prof. Kenneth Brakke of Susquehanna University concludes from the lack of evidence of alien life that we are the first intelligent life in the universe and that we will have plenty of time to colonize the entire galaxy before a second civilization can arise. See his homepage: www.susqu.edu/facstaff/b/brakke

* Professor Morgan is currently preparing a Math Chat Book based on the column. From his home page at www.williams.edu/Mathematics/fmorgan you can access previous columns and his Math Chat TV show.