关于硬币系统中无法凑出指定金额时最大金额组合等价兑换能力的证明问询
Hey everyone, let me walk through a curious coin problem I've been digging into lately.
First, a concrete example: Suppose you're using Euro coins, but you can't make exactly 2€ with whatever coins you have (meaning no combination of your coins adds up to 2€). What's the maximum total amount of money you could hold?
After working through it (and writing an algorithm to verify), the answer is 2.43€, and there are exactly three distinct ways to reach this total:
- 1€ + 50ct + 4×20ct + 5ct + 4×2ct
- 3×50ct + 4×20ct + 5ct + 4×2ct
- 50ct + 9×20ct + 5ct + 4×2ct
Here's the fascinating part: all three of these coin collections can make exactly the same set of smaller amounts. No matter which of the three you have, you can change the exact same values (and can't change the same ones too).
This got me thinking about generalizing this. Let's say we have an arbitrary coin system, and we're in a scenario where we can't make the least common multiple (LCM) of the coin denominations. I want to prove that all maximum total amount collections (that still can't make the LCM) will have identical change-making capabilities—i.e., they can all make exactly the same set of smaller amounts.
I've tested this numerically with several small coin systems, and it seems to hold true. But I'm stuck on formalizing a proof for this general case. Has anyone encountered this before, or have pointers on how to approach this proof?
备注：内容来源于stack exchange，提问作者Palehar
