Question 1: Certainly, a mindless way to solve this puzzle is to run through the triples of possible denominations, although you also must then examine all possible sums of three coins of those denominations.
To use at least a little mental ability, we start by denoting the coins, in ascending order of value, by a, b, and c. To begin, the possible combinations of coins are
(There are 10 possibilities because 10 = 5!/(3!2!), which comes from the possible permutations of 3 1's and 2 dividing lines |, which is one way of representing each combination. For example, (a,c,c) = '1| |11' since we have 1 "a", 0 "b"'s and 2 "c"'s.)
We note that none of the three sums is divisible by three, and therefore, combinations 1, 7, and 10 are impossible. We can also draw a network of the possible combinations, and partially order them, without knowing yet the values of the coins.
This means our possible combinations of 3 coins are
(More to come.)
Question 2: Surprisingly, as long as the coin denominations do not have a common factor, there will only be a finite number of values that cannot be formed. If there are just two denominations, then there is a simple formula that can be used to determine the number of missing values, and the highest such value. But for the case of three denominations, it is perhaps easiest to simply grind through the possibilities.
But how do we "grind through"? Well, suppose we write p(n) to represent "It is possible to form the value n." Suppose we have a table of values of p(n). Then, surely, one of the laws that these numbers must obey is:
p(n) = p(n-20) | p(n-9) | p(n-6)
That is, we can form n if and only if we can form at least one
of the values n-20, n-9, or n-6. Of course, we have
to be careful to interpret this formula correctly for small n. In
that case, we should interpret p of a negative number is false,
and p(0) is true (using no coins at all).
Our table, from 0 to 50, is:
| Sum | Example |
|---|---|
| 0 | 0 |
| 1 | no |
| 2 | no |
| 3 | no |
| 4 | no |
| 5 | no |
| 6 | 6 |
| 7 | no |
| 8 | no |
| 9 | 9 |
| 10 | no |
| 11 | no |
| 12 | 6+6 |
| 13 | no |
| 14 | no |
| 15 | 6+9 |
| 16 | no |
| 17 | no |
| 18 | 6+6+6 |
| 19 | no |
| 20 | 20 |
| 21 | 6+6+9 |
| 22 | no |
| 23 | no |
| 24 | 6+6+6+6 |
| 25 | no |
| 26 | 6+20 |
| 27 | 9+9+9 |
| 28 | no |
| 29 | 9+20 |
| 30 | 6+6+6+6+6 |
| 31 | no |
| 32 | 6+6+20 |
| 33 | 6+9+9+9 |
| 34 | no |
| 35 | 6+9+20 |
| 36 | 6+6+6+6+6+6 |
| 37 | no |
| 38 | 6+6+6+20 |
| 39 | 6+6+9+9+9 |
| 40 | 20+20 |
| 41 | 6+6+9+20 |
| 42 | 6+6+6+6+6+6+6 |
| 43 | no |
| 44 | 6+6+6+6+20 |
| 45 | 9+9+9+9+9 |
| 46 | 6+20 |
| 47 | 6+6+6+9+20 |
| 48 | 6+6+6+6+6+6+6+6 |
| 49 | 9+20+20 |
| 50 | 6+6+6+6+6+20 |
Surprisingly, all this work pays off. We can be convinced that 43 is the highest missing number. That's because we have a string of 6 attainable values following 43, namely 44 through 49. But that means the next string of 6, namely 50 though 55, is also attainable, simply by adding a coin of value 6. But then the next string of six can be attained in the same way, and so on.
So there are only a finite number of missing values, and 43 is the highest!
This puzzle originated from the fact that McDonald's offered Chicken McNuggets in boxes of 6, 9 or 20 pieces. There is no way to order boxes with a total of 10 or 19 pieces, obviously, and it seemed obviously that there would be infinitely many numbers that you could not form from in this way. But there are only finitely many, and 43 is the biggest one.
Back to The Coin Sum Puzzle.