Fascinating thought, but it sounds too much like chemistry to me. Can we stick to math? I’m more comfortable there.
1 Like
It’s a bit of a tangent and doesn’t solve the puzzle, but apparently the most efficient combination of 4 coin denominations you can have is 1,3,11 and 37 cent. (you can replace the 37 with 38 and get the same efficiency)
Of course that assumes you’re paying random amounts each time. In the real world adding a 99 cent coin would probably eliminate the need for most small change 
2 Likes
A similar cheat might be to have a perforated coin that can be broken into other values…
1 Like
Probably could work something out, though the day job is stealing my time today. 
Also, someone should fire that king - this is a terrible criteria for a currency.
2 Likes
I’ve worked out the following solutions for values up to 50:
1 [1]
2 [1]
3 [1, 2]
4 [1, 2]
5 [1, 2, 3]
6 [1, 2, 3]
7 [1, 2, 5]
8 [1, 3, 4]
9 [1, 2, 3, 6]
10 [1, 2, 3, 7]
11 [1, 3, 5, 6]
12 [1, 3, 5, 6]
13 [1, 2, 3, 4, 9]
14 [1, 2, 3, 7, 10]
15 [1, 3, 4, 9, 11]
16 [1, 3, 5, 7, 8]
17 [1, 2, 3, 4, 8, 13]
18 [1, 2, 3, 4, 9, 13]
19 [1, 2, 5, 8, 9, 10]
20 [1, 2, 5, 8, 9, 10]
21 [1, 2, 3, 4, 5, 10, 16]
22 [1, 2, 3, 4, 5, 11, 16]
23 [1, 2, 3, 4, 9, 13, 19]
24 [1, 2, 4, 5, 11, 13, 19]
25 [1, 2, 5, 6, 7, 15, 18]
26 [1, 2, 5, 8, 11, 12, 13]
27 [1, 2, 3, 4, 5, 10, 16, 22]
28 [1, 2, 3, 4, 5, 11, 16, 23]
29 [1, 2, 3, 7, 11, 13, 14, 16]
30 [1, 2, 3, 7, 11, 13, 14, 16]
31 [1, 2, 5, 8, 11, 14, 15, 16]
32 [1, 2, 5, 8, 11, 14, 15, 16]
33 [1, 2, 3, 4, 5, 6, 13, 19, 27]
34 [1, 2, 3, 4, 5, 11, 16, 23, 28]
35 [1, 2, 3, 6, 10, 14, 16, 17, 19]
36 [1, 2, 3, 6, 10, 14, 16, 17, 19]
37 [1, 2, 3, 7, 11, 15, 17, 18, 20]
38 [1, 2, 3, 7, 11, 15, 17, 18, 20]
39 [1, 3, 4, 9, 11, 16, 17, 19, 20]
40 [1, 3, 4, 9, 11, 16, 17, 19, 20]
41 [1, 2, 3, 5, 9, 13, 17, 19, 20, 22]
42 [1, 2, 3, 5, 9, 13, 17, 19, 20, 22]
43 [1, 2, 3, 6, 10, 14, 18, 20, 21, 23]
44 [1, 2, 3, 6, 10, 14, 18, 20, 21, 23]
45 [1, 2, 3, 7, 11, 15, 19, 21, 22, 24]
46 [1, 2, 3, 7, 11, 15, 19, 21, 22, 24]
47 [1, 2, 3, 4, 5, 6, 13, 19, 27, 33, 41]
48 [1, 2, 3, 4, 8, 12, 16, 20, 22, 23, 25]
49 [1, 2, 3, 4, 9, 14, 16, 21, 22, 24, 25]
50 [1, 2, 3, 4, 9, 14, 16, 21, 22, 24, 25]
3 Likes
I’m with you. I’ve always considered myself pretty smart but whenever I’m presented with logic puzzles or riddles I develop this kind of ADD that just doesn’t allow me to mentally parse them.
4 Likes
You’re planning something funky with dynamic lists and recursion, I hope.
Having looked the solution up, I am not convinced I agree with Mark’s categorization of this as ‘easy’. I mean, I suppose it is, but brute forcing it manually might take a while. The two solutions for 16 coins didn’t seem especially intuitive.
2 Likes
I came up with a 17 coin solution:
1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 49, 50, 52
The 16 coin solution is eluding me thus far but i think i’m on the right track
4 Likes
I think this might be one of those “I have two coins and one of them is not a nickel” {as best illustrated by the Janitor on Scrubs} i.e. read coin as one denomination. So possibly 1 is the lowest number?
Sorry, just re-read it. 2 might be the answer. “issue the smallest number of different coins”.
And to clarify my first post with an example
1+1+1 = 3
I only used one coin to do this.
Golomb rulers solve a slightly different problem where I give you 1 coin and you may give me 1 coin as change. [The original statement is that the distances between pairs of marks are the same distance apart; the coin version requires me to give you the coin corresponding to the right endpoint and you return to me a coin corresponding to the left endpoint, or no coin if the left endpoint is 0.]
For instance, with the set [1 4 6] (the example on the Wikipedia page) I can pay for the following amounts with at most 2 coins changing hands:
1 coin: I give you a 1
2 coins: I give you a 6, you give me a 4
3 coins: I give you a 4, you give me a 1
etc. You can get up to 8 (I give you two 4’s) that way. I wonder if there’s a way to use a Golomb ruler as a starting point in attacking the original problem.
1 Like
I don’t know if this would help reduce the number of coins needed, but one of my first questions my brain threw up was “can you have coins with a negative value”?!
My next thought is that you want coins that are made from metal which has a fixed value, so you can cut coins in half/quarters to provide half/quarter the value.
2 Likes
Debt tokens, I love it! You’d have to figure out some way to semi-permanently affix them to the recipient, however.
2 Likes
How about 1, 2, 3, 4, 5, 15, 25, 35, 45, 55, 65, 75, 85, 95?
14 coins.
Edit: Oops that doesn’t work. Never mind!
so. . . for X coins, the number of possible 2 coin combinations should be
X * (X+1) / 2 + X
This sets an absolute lower bound at 13 coins (104 combinations), although I suspect that there’s not a 13 coin solution
Wow, I’ve never heard of these. That’s kind of cool.
In the UK shops often have charity collection tins [and it’s funny that I still call them “tins” even though they’re made of plastic], so if you don’t want your change you may tell the cashier to donate the coins for you, but the “penny tray” is new to me.
The classic variation on the penny tray, of course:
Have a penny? Leave a penny.
Need a penny? Take a penny.
Need two pennies? Get a job.
4 Likes
Is it fair to say the answer is at most 20? Since you can only use two coins, you won’t need more than (the square root of 100) times two. If you want to cover all numbers up to a million, an upper bound will be (the square root of one million) times two = 2000. Does that make sense?
@Marktech Penny trays work great in the suburbs, but not in the inner city, because junkies just grab all the pennies and buy candy.
The opening line of the problem is false.
“In the United States at least eight coins are required to make the sum of 99 cents.”
There are at least two 6 coin US money solutions.
50,25,10,10,2,2
&
50,25,10,10,3,1
1 Like
