My Dearly Beloved, a professional philosopher, had explained to me once a fine point in the theory of just what it means to know something. I wouldn’t presume to try explaining that point (though I think I have it), but a core part of it is the thought experiment of remembering having put some change — we used a dime and a nickel — in your pocket, and finding later that you did have that same amount of money although not necessarily the same change — say, that you had three nickels instead.
That spun off a cute little side question that I’ll give to any needy recreational mathematician. It’s easy to imagine this problem where you remember having 15 cents in your pocket, and you do indeed have them, but you have a different number of coins from what you remember: three nickels instead of a dime and a nickel. Or you could remember having two coins, and indeed have two, but you have a different amount from what you remember: two dimes instead of a dime and a nickel.
Is it possible to remember correctly both the total number of coins you have, and the total value of those coins, while being mistaken about the number of each type? That is, could you remember rightly you have six coins and how much they add up to, but have the count of pennies, nickels, dimes, and quarters wrong? (In the United States there are also 50-cent and dollar coins minted, but they’re novelties and can be pretty much ignored. It’s all 1, 5, 10, and 25-cent pieces.) And can you prove it?
nebusresearch 
If you have n coins, of four possible denominations, then there are (n^3-n^2)/6 possible choices of denominations (n+1 choose 4-1). However, the maximum value is at most 25n and hence there are no more than 25n possible values.
For n> 12, this means there are more possible choices than there are possible values, hence there must be two different choices with the same value.
Constructive proof: 6x5c vs 25c + 5x1c.
LikeLike
…oops, that n^2 should just be n. But it’s the n^3 part that matters.
LikeLike
…in fact, now I look again, (n+1 choose 3) is wrong. I didn’t bother to give a full explanation of how I came to that number, and if I had, I’d have realised my error at the time.
But since the correct number of combinations is slightly MORE than (n+1 choose 3), the proof still holds.
The argument works like this: make n+1 pencil marks in a line. Between those, you have spaces for n coins:
|O|O|O|O|O|O|O|
now, pick any 3 of those pencil marks, and use those to identify a combination of coins:
– All spaces up to the first pencil mark (possibly none) are filled by 1c
– All spaces between first and second are filled by 5c
– All spaces between second and third are filled by 10c
– All spaces after third (possibly none) are filled by 25c
It’s easy to see that each possible choice of 3 pencil marks produces a different combination of coins, so there are at least (n+1 C 3) possibilities. What I missed was that this method doesn’t allow choosing zero nickels or dimes, so I undercounted the total possibilities.
The correct answer here SHOULD have been (n+3 choose 3), i.e. (n+3)(n+2)(n+1)/6. (I’ll leave proof to the readers, but I’m pretty sure I’ve got it right this time.)
Also, since the minimum value with n coins is n, and the maximum is 25n, there are actually only (24n+1) possible values from n coins.
Put those together, and it turns out that n=9 is large enough to guarantee existence of non-unique combinations.
The same sort of proof will show existence of non-unique combinations for sufficiently large n, as long as you have at least 3 denominations in integer values (or just rational values is good enough). OTOH, if your denominations are 1, sqrt(2), and pi, then no two combinations can ever have the same sum.
LikeLike
Yup! Four dimes, or, three nickels and a quarter. Both are forty cents.
I use less coins than Mr. Brent but take more money to do it. The follow-up question: Can either less money than 30 cents or less coins than four be improved upon?
–Chi
LikeLike
I’ve satisfied myself that both of those are minima. Full proof is too cumbersome to enter via margin^Wphone, but I’ll post it when I get home.
LikeLike
Okay, terminology: a “matched pair” is a set of two different combinations of coins, both of which have the same number of coins and the same total value, but different coins.
We can describe these with two quads of numbers: a1, a5, a10, a25 are the number of pennies/nickels/dimes/quarters in the first such combination, and b1…b25 ditto for the second. Being matched means that a1+5a5+10a10+25a25=b1+…+25b25 and a1+…+a25=b1+…+b25.
Obviously if ax and bx are both nonzero, we can get another matched pair with fewer coins and lower value by subtracting the same denominations from both combinations. So we know that with a minimal pair (in either total value or total coins), at least one of a1 and b1 is zero, and similarly for the other values.
Some useful lemmas:
(i) A matched pair must contain at least three different denominations altogether. (If you only have two denominations in use, then the number and value of coins uniquely defines the combination, so the combinations can’t be different.) Among other things, this means that either 1s or 25s must be included in one of the combinations.
(ii) For a minimal pair, a1 and b1 must be multiples of 5, for obvious reasons.
(iii) If all the denominations in one combination are higher (lower) than all the denominations in the other, they can’t be a matched pair: since each combination must have the same total number of coins, we can pair them up, and each coin in combination B will be strictly higher (lower) than its mate in A, so B must have a higher (lower) value than A.
(iv) Therefore, if a minimal matched pair only has three denominations involved, one combination MUST be the middle denomination (only) and the other MUST have the high and low denominations. (e.g. if we have 1s, 5s, and 25s, one will combination will be all 5s and the other will be 1s and 25s).
Now, with those lemmas established, let’s let’s look at the minimal number of coins:
If we have a minimal pair that uses pennies at all, then by (ii) one of the two combinations must have at least 5 pennies. We already know there’s a solution with 4, so this is not minimal.
If our minimal pair doesn’t use pennies, then it must use 5s, 10s, and 25s, and from (iv) above that means one combination (call it B) is all 10s and the other (A) is 5s and 25s. At least one 25 and one 5 in A requires at least 3 10s in B to match the value, but then we don’t have the right number of coins. So we need at least 3 coins in A, which means a total value of at least 25+5+5=35, which then requires at least 4 coins in B, which gets us to the solution Chiaroscure gave above.
Next, minimal value:
If our minimal pair uses 1s, then one combination (call it A) must have at least 5 1s, and from (iii) it must have at least one other coin (10c or 25c), for a total of 6 coins. This means combination B must have at least 6 coins, all of value at least 5, so its value must be at least 30c. It can only be *exactly* 30c if B has exactly 6 5s, which then leaves 5 1s and 1 25 as the only possible solution for A.
If our minimal pair does not use 1s, then we know A uses 5s and 25s, B uses only 10s. We’ve already established that the smallest solution to this requires at least 4 10s, so total value at least 40, which is worse than the solution I gave above.
Whee!
LikeLike