Saturday, January 12, 2008

The Dither Puzzle

The Dither Riddle
In the country of Oopsylvania, the unit of currency is the dither. Originally, there were three denominations of coinage, worth 1 dither, 5 dithers, and 7 dithers. However, it was discovered that the 1 dither coins included a dangerous amount of arsenic, and so one day, an emergency decree was issued and all the 1 dither coins were suddenly withdrawn.

The gum man, whose packages of gum sold for 1 dither, called an emergency meeting that night with other vendors whose business was also affected by the change. "What are we going to do?", one person cried. "There is no way for me to sell my necklaces, which cost 2 dithers. I will have to try to bundle them together."

"My brooms cost 3 dithers, and the dust pans are 4 dithers. No one can pay this price now, since the 1 dither coins are gone. What are we to do?"

"I'm not worried," said the pie man. "All my pies cost 5 dithers, so everyone who wants one can buy. And I may even sell more pies, since some of your goods have prices that are impossible to pay now!"

"Oh what am I to do?" said the onion seller. "My goods cost 6 dithers, but can't be paid for."

"At least you would only lose 1 dither if someone gave you a 5. But each of my chairs costs 9 dithers, and there's no way I can afford to accept a 5 dither coin, or even a 7 dither coin, for them," cried the caner.

"People, please calm down! Let us try to get a handle on this!" shouted the gum seller. "Until a replacement for the old 1 dither coins is available, we must adjust. But still, some prices can be paid. After all, just using the 5 dither coin, we can pay 5, 10, 15, 20 dithers or any multiple. Similarly, using the 7 dither coin gives us many more prices, 14, 21, 28 and so on. In fact, I see now that there are infinitely many prices that are still manageable."

A young cross-eyed fellow with unruly hair stood up, and cleared his throat before speaking. "May I have your attention? I think things are really not that bad at all. In fact, not only are there infinitely many prices we can charge, but there are not very many prices we can't charge. I've just worked out a way to make every price from 100 dithers up to 200 dithers." And with that he began reading a table as follows:

100 = 20 * 5
101 = 16 * 5 + 3 * 7
102 = 19 * 5 + 1 * 7
103 = 15 * 5 + 4 * 7
104 = 18 * 5 + 2 * 7
105 = ...

"Stop!" yelled an old woman. There is no need to continue. What you have just told us is enough to show that every price from 100 dithers upward can be formed. Now all we need to do is work downwards and see what prices below 100 dithers are missing."

1. Are there really only finitely many "missing" prices?
2. If so, what is the highest missing price?
3. Why did the old woman believe that the partial list, from 100 to 104, was enough information?
4. What prices are missing?