Solution to "The Dither Puzzle"

Question 1: Are there really only finitely many "missing" prices?
Yes. In this case, there are exactly 12 prices that cannot be made.

Question 2: What is the highest missing price?
The price of 23 dithers cannot be formed using 5 and 7 dither coins, and is the highest such price.

Question 3: Why did the old woman believe that the partial list was enough information?
The woman noticed that there were five consecutive prices, 100 through 104, that were achievable. But then she realized that the next five consecutive prices, 105 through 109, could be achieved simply by adding one 5 dither coin to each of the prices 100 through 104. And similarly, 110 through 114 could be achieved, and so on. So in fact, it was clear to her that every price from 100 dithers and on was achievable, and hence there were at most a finite number of missing values.

Question 4: What prices are missing?
There are just 12 missing prices: 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18, 23.

To see what is going on, note the following diagram, which lists the numbers from 1 to 35, in rows of 5. In each column, the first time a price is achieved, the corresponding value is replaced by an asterisk. But then every subsequent price in that column can be achieved by adding more 5's. So once we have an entire row of achievable prices, we are done.

         1  2  3  4  *
         6  *  8  9  |
        11  | 13  *  |
        16  | 18  |  |
         *  | 23  |  |
         |  |  *  |  |  <-- Now the whole row is filled in!
         V  V  V  V  V
      

If we have just two coin denominations, p and q, with p less than q, then we have only to make a table of the values from 1 to p q, and mark the achievable values until we fill in a row. If p and q are relatively prime, then we are guaranteed that we will reach a filled row, and hence that there is a maximum unachievable price.

But if the two coins have a common factor, such as 12 and 18, then there will be columns that never fill in, and there will be an infinite number of unachievable prices (in this case, every price that is not a multiple of 6).

In the case where p and q are relatively prime, there are formulas for the number of missing values, and for the largest missing value.

• The number of unachievable values is (p-1)(q-1)/2.
• the value of the maximum missing value is (p-1)(q-1)-1.

References:

1. James Sylvester,
   Question 7382,
   Mathematical Questions with their Solutions,
   Educational Times,
   Volume 41, page 21, 1884.

Back to The Dither Puzzle.