wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Making $1
        
(Message started by: NickH on Oct 5th, 2002, 4:03am)
Title: Making $1
Post by NickH on Oct 5th, 2002, 4:03am
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
Title: Re: NEW PUZZLE: making $1
Post by S. Owen on Oct 5th, 2002, 1:05pm
I can't make a dollar with 0 coins. Do you mean the largest number of coins that can't make a dollar?
Title: Re: NEW PUZZLE: making $1
Post by NickH on Oct 5th, 2002, 1:25pm
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?
Title: Re: NEW PUZZLE: making $1
Post by jeremiahsmith on Oct 5th, 2002, 1:59pm
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 :D
Title: Re: NEW PUZZLE: making $1
Post by NickH on Oct 5th, 2002, 2:19pm
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.
Title: Re: NEW PUZZLE: making $1
Post by Elder Dragon on Oct 7th, 2002, 1:15am
5 - penny, nickel, dime all add up to less than $1
quarter, 50 peice and dollar coin add up to more than $1
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on Oct 7th, 2002, 8:50am
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.
Title: Re: NEW PUZZLE: making $1
Post by NickH on Oct 7th, 2002, 12:22pm
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
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on Oct 8th, 2002, 2:45am
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. ;)
Title: Re: NEW PUZZLE: making $1
Post by NickH on Oct 8th, 2002, 11:00am
Any chance you might share your solution?  Was it too big to fit in the margin?   ;)

Nick
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on Oct 10th, 2002, 9:37am
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.
Title: Re: NEW PUZZLE: making $1
Post by NickH on Oct 10th, 2002, 11:55am
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
Title: Re: NEW PUZZLE: making $1
Post by Kozo Morimoto on Oct 10th, 2002, 2:29pm
So how does this relate to the (2nd) smallest product of 2 primes separated by 4?
1 x 5 = 5
3 x 7 = 21 ?
Title: Re: NEW PUZZLE: making $1
Post by S. Owen on Oct 10th, 2002, 2:44pm
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?
Title: Re: NEW PUZZLE: making $1
Post by NickH on Oct 10th, 2002, 3:22pm
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
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on Oct 11th, 2002, 5:11am
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.
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on Oct 11th, 2002, 5:17am
S = {3, 1}, SIN = 2.
Oh well...
Title: Re: NEW PUZZLE: making $1
Post by Kozo Morimoto on Oct 12th, 2002, 6:19am
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.
Title: Re: NEW PUZZLE: making $1
Post by NickH on Oct 12th, 2002, 7:57am
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
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on Oct 14th, 2002, 4:30am
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.
Title: Re: NEW PUZZLE: making $1
Post by Kozo Morimoto on Oct 14th, 2002, 8:51pm
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!)
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on Oct 15th, 2002, 3:28am
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).
Title: Re: NEW PUZZLE: making $1
Post by Kozo Morimoto on Oct 15th, 2002, 7:06pm
Check out
http://www.rba.gov.au/CurrencyNotes/people_on_notes.html
for our notes.

They are plastic and supposed to be wash proof and rip/torn proof.  They are all different in size (unlike the green back) and look like toy money!
Title: Re: NEW PUZZLE: making $1
Post by Burton on May 2nd, 2003, 1:47am

on 10/10/02 at 09:37:22, 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...
:)
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on May 2nd, 2003, 6:06am
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!  :D
Title: Re: NEW PUZZLE: making $1
Post by Burton on May 2nd, 2003, 3:04pm
The term 'brute force' does imply a certain lack of aesthetics...I'm figuring you start out with n all in pennies, and if the sum isn't 1, you try n-1 pennies and 1 nickel.  And so on.  My real question is how your program would 'know' it had exhausted every possible combination, giving a result of 'no solution'.  A hint to the ugly algorithm would be greatly appreciated.
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on May 2nd, 2003, 3:38pm
The process is quite different. I start from nothing and add a penny, then another one, and so on, until I achieve my goal or have more pennies than the allowed number of coins.

If you register, I'll send you the source in a private message. It's a program for awk, by the way, but understandable for non-awkers also, I hope.
Title: Re: NEW PUZZLE: making $1
Post by SnugglySoft on May 2nd, 2003, 4:07pm
Sorry, I had registered a while back, but using a different browser, and I was too lazy to login because I had misplaced my password.  I'll make sure my profile has me showing my e-mail address.  I've never coded in awk before; hopefully I'll be able to decipher the logic.  Thanks for following up so readily on something you did last October.   ;D
Title: Re: NEW PUZZLE: making $1
Post by wowbagger on May 5th, 2003, 2:41am

on 05/02/03 at 16:07:30, SnugglySoft wrote:
Thanks for following up so readily on something you did last October.   ;D

No problem.

Well, at least not in this case as I not only found the script, but also understood what I was doing back then!
Remarkable...  ;D
Title: Re: Making $1
Post by foreverundecided on May 10th, 2007, 7:35am
Hi,
 Is this really an easy one?. Comes under the easy puzzles. I have been at it for a while and given up for now.
Title: Re: Making $1
Post by rmsgrey on May 10th, 2007, 8:48am

on 05/10/07 at 07:35:13, foreverundecided wrote:
Hi,
 Is this really an easy one?. Comes under the easy puzzles. I have been at it for a while and given up for now.

It's "easy" in the sense that it doesn't need large leaps of logic or deep insights to solve - it's fairly easy to find combinations of change that'll use the right number of coins, so the only difficulty comes in having the patience to work at it.

It's not inconceivable that a more sophisticated solution exists, but (computer-aided) brute force appears to do the trick adequately.
Title: Re: Making $1
Post by Eigenray on May 10th, 2007, 12:31pm
My solution is:

[hideb]f[k_] = 1/(1 - x^k y);
First@Flatten@Position[CoefficientList[SeriesCoefficient[Series[ f[1]f[5]f[10]f[25]f[50]f[100], {x, 0, 100}], 100]/y, y], 0],[/hideb]

because [hide]the coefficient of xayb is the number of ways to have b coins adding up to a cents[/hide].

Also, I think NickH's solution is more elegant than people appreciated (4.6 years ago!).  You can even do it in your head if you know the following: If m,n are relatively prime positive integers (here 4 and 9), then (m-1)(n-1)-1 is the largest number not representable in the form am+bn, with a,b nonnegative integers.

[Edit]But it doesn't seem to be complete, because it's not exactly equivalent to finding

Quote:
the largest value that cannot be obtained by plugging non-negative integers into 4b + 9c + 24d + 49e + 99f.

The largest such value is 23.  But if we only had the coins 1,5,10, we'd still get 23 here, even though the answer in this case is surely not 77.

Rather, we need to determine the values 100-x that can't be obtained as
100 - x  = 4b + 9c + 24d + 49e + 99f
by non-negative integers b,c,d,e,f with b+c+d+e+f <= x.
So we can easily see that 23 (x=77) is not representable in this way.  And if 20 <= x < 77, then 100-x > 23, so we can write
4b+9c = 100-x
for non-negative b,c, with
b+c <= 1/4 (4b+9c) = 25 - x/4 <= x.
And for 10 <= x <= 20 we have
80 = 0*9 + 20*4
81 = 1*9 + 18*4
82 = 2*9 + 16*4
...
90 = 10*9 + 0*4.
So it remains only to consider x=1,...,9 (which are precisely the values for which {1,5,10} cent coins do not suffice).


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board