Author |
Topic: Making $1 (Read 4479 times) |
|
Burton
Guest
|
 |
Re: NEW PUZZLE: making $1
« Reply #25 on: May 2nd, 2003, 3:04pm » |
 Quote  Modify
 Remove
|
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.
|
|
 IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender: 
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #26 on: May 2nd, 2003, 3:38pm » |
Quote Modify
|
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.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
SnugglySoft
Newbie
Hi there!
Gender:
Posts: 1
|
|
Re: NEW PUZZLE: making $1
« Reply #27 on: May 2nd, 2003, 4:07pm » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: making $1
« Reply #28 on: May 5th, 2003, 2:41am » |
Quote Modify
|
on May 2nd, 2003, 4:07pm, SnugglySoft wrote:| Thanks for following up so readily on something you did last October. |
|
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...
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
foreverundecided
Newbie
Posts: 1
|
|
Re: Making $1
« Reply #29 on: May 10th, 2007, 7:35am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
  
Gender:
Posts: 2873
|
|
Re: Making $1
« Reply #30 on: May 10th, 2007, 8:48am » |
Quote Modify
|
on May 10th, 2007, 7:35am, 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Making $1
« Reply #31 on: May 10th, 2007, 12:31pm » |
Quote Modify
|
My solution is:
| hidden: | 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], |
because the coefficient of xayb is the number of ways to have b coins adding up to a cents.
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).
|
| « Last Edit: May 10th, 2007, 1:38pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print