Solution to Puzzle 1: It's hard to see an analytic way to solve this puzzle.
There are the "usual suspects", though, to check as candidates. Obviously, the values (1,2,3,4) fail at 17.
Another arithmetic series to try is (1,4,7,10), but this only gets us to 22, failing at 23.
Oddly, the arithmetic series (1,3,5,7), also only gets to 22, failing at 23.
If we try the binary series (1,2,4,8), we surprisingly fail sooner, at 16! A little thought shows that, for a vending machine that accepts N coins, the values (1,2,...,N) will achieve all values from 1 to N2, while the series (1,2,4,8,...,2N-1) will achieve all values up to 2N-1, so the binary series will outdo the arithmetic series values of N from 5 on.
Another approach is a sort of "stingy" algorithm, in which we don't seek a new value until we absolutely must. So we start with a value of 1, and we can form 1, 2, 3 and 4. Now to go on, we must have a way of forming 5, and under this approach, we actually just decide that the next chip value will be 5. This gives us the values 5, 6=5+1, 7=5+1+1, 8=5+1+1+1, and now we need a value of 9. The next value we need is 13, and we end up reaching 16=13+1+1+1, and failing at 17. So no good news here! (1,5,9,13) fails at 17.
Our experience with the stingy algorithm suggests we separated our values too widely. Another sequence that comes to mind is the integer sum sequence, beginning (1,3,6,10). Using these values, we are able to construct all values from 1 to 33, failing at 34.
Yuen-Yick Kwan devised a greedy algorithm, with which he searched for good coin denominations. He considered having from 1 to 6 denominations for the 4-slot machine. The results for his search were
| Denominations | #1 | #2 | #3 | #4 | #5 | #6 | Fails |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 5 | |||||
| 2 | 1 | 4 | 11 | ||||
| 3 | 1 | 4 | 9 | 24 | |||
| 4 | 1 | 4 | 9 | 15 | 41 | ||
| 5 | 1 | 4 | 9 | 15 | 39 | 65 | |
| 6 | 1 | 4 | 9 | 15 | 39 | 65 | 100 |
Yuen-Yick Kwan points out that he used a program to search for his results, and that he made the plausible assumption that the solution for N+1 denominations involves the solution for N denominations plus one new denomination. That is how he arrived at the numbers listed here, but he points out that this approach got an answer worse than the one posted for puzzle 2.
Solution to Puzzle 2: The sequence of values (1,4,7,8) first fails at 25.
Back to The Vending Machine Puzzle.