Author |
Topic: Making $1 (Read 4476 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
Another oldie but goodie...
Given the standard US coins (1, 5, 10, 25 cent), what is the smallest number of coins with which you CANNOT make a dollar, assuming you can use any number of coins, in any mix of denominations?
Nick
|
| « Last Edit: Sep 20th, 2003, 9:26pm by Icarus » |
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
 |
Re: NEW PUZZLE: making $1
« Reply #1 on: Oct 5th, 2002, 1:05pm » |
 Quote  Modify
|
I can't make a dollar with 0 coins. Do you mean the largest number of coins that can't make a dollar?
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
 |
Re: NEW PUZZLE: making $1
« Reply #2 on: Oct 5th, 2002, 1:25pm » |
Quote Modify
|
Nice try! There is no largest number. I mean the smallest non-zero number of coins, of course. What is the smallest n such that with n each of the standard denominations, we cannot select n coins to make a dollar?
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: NEW PUZZLE: making $1
« Reply #3 on: Oct 5th, 2002, 1:59pm » |
Quote Modify
|
If n is one, we have one penny, one nickel, one dime, and one quarter, and you can't make a buck with that. Perhaps you need to phrase this better 
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PUZZLE: making $1
« Reply #4 on: Oct 5th, 2002, 2:19pm » |
Quote Modify
|
I should be more careful, shouldn't I?!
Include the half dollar and dollar coins in the list of standard denominations. So n = 1, 2, 3, 4 are catered for.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Elder Dragon
Guest
|
5 - penny, nickel, dime all add up to less than $1
quarter, 50 peice and dollar coin add up to more than $1
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #6 on: Oct 7th, 2002, 8:50am » |
Quote Modify
|
I understand the puzzle in the following way:
You are given n coins of denominations 1, 0.5, 0.25, 0.1, 0.05 and 0.01 (6n coins altogether). You are then asked to choose n out of these 6n coins that sum up to exactly 1. What is the smallest n for which this is impossible?
If that's what you meant, there's obviously no upper limit to n.
My answer for the smallest n is the smallest product of two primes that differ by 4.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PUZZLE: making $1
« Reply #7 on: Oct 7th, 2002, 12:22pm » |
Quote Modify
|
Elder Dragon -- the coins you use can be in any mix of denominations. So 5 is not the answer, as $1 = 50c + 25c + 2*10c + 5c.
wowbagger -- your understanding of the puzzle is as I intended. Clearly there is no upper limit for n. As for your answer, do you mean the second smallest such product?
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #8 on: Oct 8th, 2002, 2:45am » |
Quote Modify
|
Whoops! You're right, of course. 
Somehow I missed the smallest such pair of primes - guess I should have checked my feigned cleverness with a short program. 
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
 |
Re: NEW PUZZLE: making $1
« Reply #9 on: Oct 8th, 2002, 11:00am » |
Quote Modify
|
Any chance you might share your solution? Was it too big to fit in the margin?
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #10 on: Oct 10th, 2002, 9:37am » |
Quote Modify
|
My program that helped me in finding valid combinations of coins or deciding there is no solution is simply looping over possible numbers of coins. It's rather unaesthetic, so:
For those who are interested in possible solutions (hidden by colour):
n: number of coins in the sequence 1.0, 0.5, 0.25, 0.1, 0.05, 0.01
1: 1, 0, 0, 0, 0, 0
2: 0, 2, 0, 0, 0, 0
3: 0, 1, 2, 0, 0, 0
4: 0, 0, 4, 0, 0, 0
5: 0, 1, 1, 2, 1, 0
6: 0, 0, 3, 2, 1, 0
7: 0, 0, 2, 5, 0, 0
8: 0, 0, 2, 4, 2, 0
9: 0, 0, 1, 7, 1, 0
10: 0, 0, 0,10, 0, 0
11: 0, 0, 0, 9, 2, 0
12: 0, 0, 0, 8, 4, 0
13: 0, 0, 0, 7, 6, 0
14: 0, 0, 0, 6, 8, 0
15: 0, 0, 0, 5,10, 0
16: 0, 0, 0, 4,12, 0
17: 0, 0, 0, 3,14, 0
18: 0, 0, 0, 2,16, 0
19: 0, 0, 0, 1,18, 0
20: 0, 0, 0, 0,20, 0
21: 0, 0, 0, 3,13, 5
22: 0, 0, 0, 2,15, 5
23: 0, 0, 0, 1,17, 5
24: 0, 0, 0, 0,19, 5
25: 0, 0, 0, 7, 3,15
26: 0, 0, 0, 6, 5,15
27: 0, 0, 0, 1,16,10
28: 0, 0, 0, 0,18,10
29: 0, 0, 0, 3,11,15
30: 0, 0, 0, 2,13,15
31: 0, 0, 0, 1,15,15
32: 0, 0, 0, 0,17,15
33: 0, 0, 0, 3,10,20
34: 0, 0, 0, 2,12,20
35: 0, 0, 0, 1,14,20
36: 0, 0, 0, 0,16,20
37: 0, 0, 0, 3, 9,25
38: 0, 0, 0, 2,11,25
39: 0, 0, 0, 1,13,25
40: 0, 0, 0, 0,15,25
41: 0, 0, 0, 3, 8,30
42: 0, 0, 0, 2,10,30
43: 0, 0, 0, 1,12,30
44: 0, 0, 0, 0,14,30
45: 0, 0, 1, 3, 1,40
46: 0, 0, 0, 2, 9,35
47: 0, 0, 0, 1,11,35
48: 0, 0, 0, 0,13,35
49: 0, 0, 0, 3, 6,40
50: 0, 0, 0, 2, 8,40
51: 0, 0, 0, 1,10,40
52: 0, 0, 0, 0,12,40
53: 0, 0, 0, 3, 5,45
54: 0, 0, 0, 2, 7,45
55: 0, 0, 0, 1, 9,45
56: 0, 0, 0, 0,11,45
57: 0, 0, 0, 3, 4,50
58: 0, 0, 0, 2, 6,50
59: 0, 0, 0, 1, 8,50
60: 0, 0, 0, 0,10,50
61: 0, 0, 0, 3, 3,55
62: 0, 0, 0, 2, 5,55
63: 0, 0, 0, 1, 7,55
64: 0, 0, 0, 0, 9,55
65: 0, 0, 0, 3, 2,60
66: 0, 0, 0, 2, 4,60
67: 0, 0, 0, 1, 6,60
68: 0, 0, 0, 0, 8,60
69: 0, 0, 0, 3, 1,65
70: 0, 0, 0, 2, 3,65
71: 0, 0, 0, 1, 5,65
72: 0, 0, 0, 0, 7,65
73: 0, 0, 0, 3, 0,70
74: 0, 0, 0, 2, 2,70
75: 0, 0, 0, 1, 4,70
76: 0, 0, 0, 0, 6,70
77: no solution
78: 0, 0, 0, 2, 1,75
79: 0, 0, 0, 1, 3,75
80: 0, 0, 0, 0, 5,75
81: no solution
82: 0, 0, 0, 2, 0,80
83: 0, 0, 0, 1, 2,80
84: 0, 0, 0, 0, 4,80
85: no solution
86: no solution
87: 0, 0, 0, 1, 1,85
88: 0, 0, 0, 0, 3,85
89: no solution
90: no solution
91: 0, 0, 0, 1, 0,90
92: 0, 0, 0, 0, 2,90
93: no solution
94: no solution
95: no solution
96: 0, 0, 0, 0, 1,95
97: no solution
98: no solution
99: no solution
100: 0, 0, 0, 0, 0,100
I'm sure you can deduce which way I'm looping.
|
| « Last Edit: Oct 10th, 2002, 9:38am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PUZZLE: making $1
« Reply #11 on: Oct 10th, 2002, 11:55am » |
Quote Modify
|
Here's an analytical solution that takes you most of the way there...
Suppose we have x coins, comprised of a pennies, b nickels, c dimes, d quarters, e half dollars, and f dollars, with a,b,c,d,e,f >= 0.
Then a + 5b + 10c + 25d + 50e + 100f = 100 and x = a + b + c + d + e + f.
Therefore 4b + 9c + 24d + 49e + 99f = 100 - x.
We seek the smallest value of x such that the above equation has no solution. In other words, we seek the largest value of 100 - x with no solution. That is, the largest value that cannot be obtained by plugging non-negative integers into 4b + 9c + 24d + 49e + 99f.
This is not as intractable, and it's quite easy to verify that 23 is the highest such value.
Therefore the smallest number of coins with which it is impossible to make a dollar with is 77.
Nick
|
| « Last Edit: Oct 10th, 2002, 11:57am by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Kozo Morimoto
Junior Member
Posts: 114
|
|
Re: NEW PUZZLE: making $1
« Reply #12 on: Oct 10th, 2002, 2:29pm » |
Quote Modify
|
So how does this relate to the (2nd) smallest product of 2 primes separated by 4?
1 x 5 = 5
3 x 7 = 21 ?
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PUZZLE: making $1
« Reply #13 on: Oct 10th, 2002, 2:44pm » |
Quote Modify
|
1 isn't considered prime, so the second smallest product of primes that differ by 4 is 7 x 11 = 77.
Nick and wow - is this just a coincidence or is there a reason that the solution must be the product of two primes that differ by 4?
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PUZZLE: making $1
« Reply #14 on: Oct 10th, 2002, 3:22pm » |
Quote Modify
|
Kozo and S. Owen, I'll be interested to hear what wowbagger has to say, but I believe he was simply trying to be cryptic!
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #15 on: Oct 11th, 2002, 5:11am » |
Quote Modify
|
That's right Nick, I simply didn't want to give away the solution without a bit of thinking. Looks like it takes more than one bit...
I think it's only a coincidence that the solution has this form. Actually, I tried to look for a variant using the set of coins we have here in Germany (euros):
2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01.
In a way it's easier as you have 8 different coins. If you take all 8 and try to make 2 euros, you end up with n = 201 as the "smallest impossible number" (SIN). If you don't use 2-cent-coins, SIN = 185. If you don't use 2-euro-coins and aim at making 1 euro, SIN = 3 because of 0.2 instead of 0.25.
Maybe the inverse problem is more interesting:
Determine an ordered set S of s different values {c1, c2, ..., cs} (c1 > cs) such that the SIN for making c1 has a certain value, e.g. SIN = 42. To exclude trivial answers, S and SIN should be subject to the conditions c1 / cs > SIN > 1.
At first sight, I'd conjecture the SIN is always odd. I wonder whether that can be proven.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
 |
Re: NEW PUZZLE: making $1
« Reply #16 on: Oct 11th, 2002, 5:17am » |
Quote Modify
|
S = {3, 1}, SIN = 2.
Oh well...
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Kozo Morimoto
Junior Member
Posts: 114
|
|
Re: NEW PUZZLE: making $1
« Reply #17 on: Oct 12th, 2002, 6:19am » |
Quote Modify
|
So is there an elegant solution to this problem or does it necessitate a brute force approach?
In Australia we only have 5c, 10c, 20c, 50c, $1 and $2 and wanted to know what the solution would be.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PUZZLE: making $1
« Reply #18 on: Oct 12th, 2002, 7:57am » |
Quote Modify
|
Well, the solution I presented reduces the brute force needed to a manageable level! It is useful when considering a larger number of coins; say, larger than 50.
For Australian coinage, I assume there is a 1 cent coin. Clearly the $2 coin is irrelevant.
By inspection, it is clear that the solution is 3 coins!
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #19 on: Oct 14th, 2002, 4:30am » |
Quote Modify
|
The $2 coin is not irrelevant!
If you disregard it, you try to make $1, if you consider it part of your set of coins, you have to make $2 in total, so for n = 3 you can use $1 + 50c + 50c.
I assume you're always trying to make $1 whereas I'm trying to make c1, the highest value of a single coin. 
Kozo, you can make $2 using coins down to 5c for all numbers of coins up to (and including) 40.
If you include the 1c coin, you end up with the same set of coins I used in a previous post, with SIN = 185.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Kozo Morimoto
Junior Member
Posts: 114
|
|
Re: NEW PUZZLE: making $1
« Reply #20 on: Oct 14th, 2002, 8:51pm » |
Quote Modify
|
Sorry to disappoint, but us Aussies don't have 1c nor do we have the 2c coin. Everything is rounded to the nearest 5c and paid for that way. 5c coin is the smallest denomination here in Oz. (a little trivia for you foreigners!)
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #21 on: Oct 15th, 2002, 3:28am » |
Quote Modify
|
Thanks for the additional info!
After searching for more information regarding Australian money, I have to say I really enjoy the design of your banknotes, especially the $10 bill.
For those interested, you can have a look at the euro banknotes and coins at http://www.euro.ecb.int/en/section.html (use the links on the left).
|
| « Last Edit: Oct 15th, 2002, 4:19am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Burton
Guest
|
|
Re: NEW PUZZLE: making $1
« Reply #23 on: May 2nd, 2003, 1:47am » |
Quote Modify
 Remove
|
on Oct 10th, 2002, 9:37am, wowbagger wrote:My program that helped me in finding valid combinations of coins or deciding there is no solution is simply looping over possible numbers of coins. It's rather unaesthetic, so:...
I'm sure you can deduce which way I'm looping. |
|
I'd love to look at your source code for that one...
:)
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #24 on: May 2nd, 2003, 6:06am » |
Quote Modify
|
I seriously doubt that!
As I said, it is rather unasthetic!
But I guess you meant the deduce-the-way-I'm-looping "challenge". Well, it's not much of a challenge anyway, so why bother? Actually, it might even be easier to find out by looking at my solutions than by brooding over the source code!
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print