Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1998). He can be contacted at [email protected].
He said his name was Eli Tyler. "I manufacture money," he said, his ready grin making his eyes gleam. He was wearing a shirt with beautiful coins from around the world.
"I don't mean that I counterfeit it, but that I help governments design their coins. Here are a few of them." He pointed at five coins on his shirt. "I hope for some more. My problem is that the president of the new country Mujikhistan is a mathematician."
"What a terrible problem!" Ecco said, matching Tyler's grin.
"Yes, because he has this idea about saving money by minimizing the number of coins he needs to make," Tyler said. "He hasn't yet decided how many denominations of coins to mint, but he wants it to be the case that the average number of coins needed for a purchase should be as small as possible.
"For example, if the only denominations were pennies (each worth 1 cent) and nickels (worth 5 cents), then forming 99 cents would require 19 nickels and 4 pennies for a total of 23 coins altogether. The average number altogether would be the average of 1 (for 1 cent), 2 (for 2 cents),..., 2 (for 6 cents),..., 6 (for 22 cents), 7 (for 23 cents),..., 23 (for 99 cents). That average is about 11.6. On the other hand, if the two denominations were pennies and dimes (worth 10 cents), then forming 99 cents would require 9 dimes and 9 pennies for a total of 18 coins altogether. The average number of coins for forming 1 to 99 would then be about 9.1. So, dimes and pennies would be better, but then elves and pennies would be even better, where an elf is worth 11 cents. This president seems willing to consider any denomination at all if it saves money to his mint. 'If the denominations come out to be 37 cents, 22 cents, 4 cents, and a penny, I would be happy. The people's mathematics level would improve,' he says. Can you imagine?"
"I bet you'd like this guy, uncle," 12-year-old Liane said to Ecco.
"Except that he rolls heads when he's in a less numerate mood," Ecco said with a frown.
"These denominations should have some special properties," Tyler went on. "For example, we want it to be the case that the fewest number of coins can always (or nearly always) be obtained by counting out the money according to the following intuitive method: The first coin is of the largest denomination that is less than or equal to the amount desired; the second coin is of the largest denomination that is less than or equal to the amount desired less the value of the first coin; the third coin is of the largest denomination that is less than or equal to the amount desired less the value of the first two coins; and so on until the amount desired is reached. We call such a set 'intuitive.' For example, the denominations 25, 5, and 1 are intuitive because it is never bad to start with 25 if the amount desired is over 25 and it is never bad to start with 5 if the amount desired is over 5 and under 25. On the other hand, if the denominations were 25, 10, and 1, then 30 cents would best be handled by 3 dimes, rather than a quarter and 5 pennies. Such a set of denominations is called 'nonintuitive.' We are most interested in intuitive sets.
"To help him decide how many denominations to create, the president has asked me to find: 1. the best set of denominations that consist of three coin values, including pennies; 2. four denominations, including pennies; and 3. five denominations, including pennies. He wants me to consider all prices between 1 and 99 to be equally likely and the goal is to minimize the average number of coins needed."
Liane and Ecco set to work.
I went back to reading Robert Bly and was surprised that they came up with an answer in a little over an hour.
Reader: Ecco was able to produce a three-denomination (including pennies) set that required on the average under 5.4 coins to pay for any item costing between 1 and 99 cents; under 4.2 coins for a four-denomination set including pennies; under 3.6 for a five-denomination set including pennies; and under 3.3 for a six- denomination set. Can you do better?
"What strange collections of denominations, hardly a 5 or 10 among them -- and here you propose a 44 cent coin!" Tyler exclaimed when looking at the result. "The next generation in Mujikhistan will consist of bright people or calculator toters. Tell me, is nonintuitive counting ever useful in your scheme?"
"Yes, I believe it's unavoidable," Ecco said. "The denomination sets we gave you are the best we could find using an intuitive counting method, but some of those sets are in fact nonintuitive, though only a few prices are best served by nonintuitive counting."
Reader: In Ecco's case, the five- and six-denomination sets were nonintuitive. Ecco doesn't know whether his belief is true though. Can you resolve the question either way?
"I'll have to think about that one," Tyler said. "But I have another question. I believe that with inflation, it will soon be the case that nothing will cost less than 5 cents and that in fact every item will cost a multiple of 5 cents. In that case, could you design me the best coin denominations that are multiples of 5 cents?"
Reader: Ecco was able to design a three-denomination set requiring an average of less than 2.6 coins per purchase. For the best four-denomination set, the average was less than 2.2 coins per purchase. For the best five-denomination set, the average was less than 2 coins per purchase. Can you do better? The results suggest that Tyler may have to design a 65 cent coin.
After Tyler left, Ecco turned to me. "Let's go back to the case where items can cost as little as a penny," Ecco said. "But now assume that the seller always has coins himself. So, for every price, we would like to minimize the sum of the number of coins passed from the buyer to the seller and the coins returned in change. We call this sum the 'exchange number.' Notice that when exchanges are always possible, pennies themselves may not be necessary since an item costing a single penny may, if these coins are available, be purchased by paying with a 5-penny coin and receiving two 2-penny coins in return for a total exchange number of three. Assuming exchange numbers as the metric, what would then be the best three-denomination, four- denomination, five-denomination, and six-denomination sets; that is, the ones that minimize the average exchange numbers?"
I had no idea.
Reader: Would you like to attempt this one?
Last Month's Solution
The best way to preserve overall diversity is to isolate the tracts as much as possible. That is what saved the Australian marsupials, until people affected the balance there. So, among the connected topologies, a linear one seems to be the best. The unknowns can have a large effect. Dominant males reduce diversity since the dominant male propagates his genes. Linkage also reduces diversity.
So, it takes roughly 275 generations for all diversity to disappear in the case of a linear topology, random mating (no dominant male), and unlinked traits.
By contrast, it takes only about 25 generations for all diversity to disappear if every tract is connected directly to every other, males breed according to dominance, and all traits are linked. Of these effects, dominance breeding is the worst for diversity, though it may convey other benefits.
Reader Notes
Several readers found even faster escape routes in the "Escape" puzzle (DDJ, August 2000) than the prisoner: Jason Murray, Dennis L. Cumro, Steve Kietzman, Patrick R. Schonfeld, Robert Morrison, and Jimmy Hu.
Patrick R. Schonfeld (with Jimmy Hu close behind) described the fastest scheme at 3 minutes and 16 seconds. The method would go faster if the prisoner could safely reach a cell at the instant a robot is leaving the cell. Here's how Schonfeld describes it:
Robot 1 at (4, 4) is passed by the prisoner at t=31.
Robot 2 at (26, 8) is passed by the prisoner at t=99.
Robot 3 at (15,12) is passed by the prisoner at t=145.
Robot 4 at (18,16) is passed by the prisoner at t=175.
Robot 5 at (20,20) is passed by the prisoner at t=195.
Schonfeld also described a 24-minute cycle that eliminates the chance of escape for all prisoners below the 20th row. Here was his basic suggestion: "The 4-part cycle consists of: 1. Three robots patrol rows 1-18 in the standard way (but faster), while robots 4 and 5 are stationary at opposite ends of rows 19 and 20, respectively; 2. Robot 4 does two passes of row 19; 3. Robot 5 does two passes of row 20. Note that with this cycle, the cells in rows 19 and 20 are checked twice per cycle. The 4th part of the cycle consists of the robots being stationary for 10 seconds to complete 24 minutes."
DDJ
