返回题库

硬币组合不可唯一确定的最小硬币数

Coin Identifier

专题
Probability / 概率
难度
L2

题目详情

Brian 口袋里有 0.60 美元,只由 5 分、10 分、25 分硬币组成。若他共有 NN 枚硬币,求最小的 NN 使得这些硬币的具体张数(各面额多少枚)无法被唯一确定。

Brian walks to the convenience store with 0.60inhispocket.Hismoneyismadeofsolelynickels,dimes,andquarters.IfBrianhas0.60 in his pocket. His money is made of solely nickels, dimes, and quarters. If Brian hasNcoinsinhispocket,findthesmallestvalueofcoins in his pocket, find the smallest value ofN$ such that the quantities of each type of coin in Brian's pocket can't be uniquely identified.

解析

最小为 N=6N=6

例如 0.40 可用 4 枚硬币表示为:1 枚 25 分 + 3 枚 5 分,或 4 枚 10 分。把两种方案都再加 2 枚 10 分即可得到 0.60 且硬币数同为 6。


Original Explanation

Clearly, N=1N = 1 and N=2N = 2 don't work, as you can't obtain 0.60fromjustoneortwocoinsofthesedenominations.For0.60 from just one or two coins of these denominations. ForN = 3,wecanseethat, we can see that2quartersandquarters and1$ dime work. There are no other ways to obtain the sum besides this.

Now, note that 0.400.40 is the smallest denomination that can be written in two different ways using the same amount of coins. Namely, we can use 44 coins to write 0.400.40 as 11 quarter and 33 nickels OR 44 dimes. Therefore, we can just append 22 dimes to each of these combinations, and we get that N=6N = 6 is the smallest value for which this is true.

To verify 0.400.40 is the smallest value, we know that the number is at least 0.250.25, as otherwise we can't utilize quarters, so test 0.300.30 and 0.350.35 and see that they don't work.