This is one of the common factoid that cirulates on “Internet lists,” as I call them–that $1.19 (three quarters, four dimes, and four pennies)is the largest amount of money possible (in coins) that can not make change for an even dollar.
My question:
Let’s say we weren’t aware of this factoid, and we were trying to figure it out. Is there a way of deducing it, or is this one of those problems that would have to be ground out by hand?
Um… why can’t I have a pocket full of one dollar coins?
Once in a while you can get shown the light
in the strangest of places
if you look at it right…
I think the answer can be derived mathematically. The technique would be to use “Diophantine equations”, which are algebraic equations constrained to integer solutions. You would express everything in pennies.
jrf
I’ve derived that one myself, lots of times, when I can’t remember it. I didn’t use any equations though.
Just start big: quarters. You can have 3 of those without change. Okay, going down: Dimes: can’t have more than 4, or you’d have 5, which with 2 quarters is change. So, 4 dimes.
Now, no nickels, else you’d have 3 quarters, 2 dimes and a nickel. So, that leaves pennies, and you can have up to 4 pennies before you run into the same problem as nickels.
TheNerd, I think your reasoning is not quite correct.
Because nine dimes, one quarter and four pennies would also fit the answer.
I don’t think Nerd’s reasoning holds up either, while $1.19 may be the correct answer, I can’t seem to come up with anything to prove it. I’m trying to find a proof, but not having much luck.
There’s nothing wrong with the way TheNerd reasoned his way to one solution. That was how I approached the question. And *Arnold supplied the alternate combination for the same total of $1.19. Somehow you have to arrive at 0.95 with no coin below 0.10 before adding in other coins. You can’t do it without at least one quarter, so TheNerd’s approach just gets to the same place quicker.
Can I use a bit?
Maybe I’m being a bit anal about it, but just because you can come up with one combination that seems like the highest amount possible, does not mean that the value or combination of coins you came up with is in fact the correct answer.
I guess I don’t see how TheNerd’s answer demonstrates that it is impossible to have a different combination of coins that totals greater than $1.19 but can’t be broken into one dollar.
Mr Sleep,
*TheNerd made a reasoned approach that gets one as close as one can be to a dollar figure without getting into the smaller units, that is the approach I’m inclined to take. Arnie (I hope abbreviation doesn’t bother you, Arnold; say so and I’ll stop) pointed out another path to the same point. So we’ve combined a reasoned approach with an empirical reevaluation and arrived at the same point.
Mr Sleep said:
TheNerd provided one solution and Arnold provided the other. The question does not specifically address the combination of coins, rather the total. Both are right.
I might go to sleep now (Hah! Good luck people.).
Apparently I’m just having a sloppy code month - let me know if something turns out wholly unintelligeable.
I hate to beat a dead horse, on the other hand, I have ten minutes to kill so…
I understand the approach TheNerd took to the question, it seems like a logical way to do it. What I’m looking for is proof (ie, algorithmic or otherwise, preferably not brute force) that any combination of coins that totals to greater than $1.19 can be broken into an even dollar. You can’t determine that $1.19 is the answer without proving the above.
I’ve been playing around with it, and can’t come up with anything. I’m hoping that someone out there has such a proof, and I’m hoping that they’ll post a link or something.
Neither can I. In fact I still need to take the course that comes before differential equations. C’mon, will one of you sharpies out there give us a hand? 
“What’s right is only half of what’s wrong
and I want a short-haired girl
Who sometimes wears it twice as long”
George Harrison - Old Brown Shoe
My math is weak, but this smells like an version of the integer packing problem, which is NP-complete. I suspect that the problem is not solvable except by brute force.
Not only that, but as an NP-complete problem gets larger even brute force will fail, even for the fastest computers.
He’s the sort to stand on a hilltop in a thunderstorm wearing wet copper armor, shouting ‘All Gods are Bastards!’
I’m not going to bother with using any kind of Diophantine equations, it’s been a while and I’d be a little rusty. Not to mention that seems kind of messy.
I think it’s clear that this can be done with $1.19. I don’t think TheNerd’s approach is sufficient, though, for the above reasons.
Anyway:
$1.20 and anything greater doesn’t work:
Take away 0, 1, 2, 3, or 4 pennies, so that the number of pennies is divisible by 5.
Take away all the quarters and half dollars, leaving pennies, nickels and dimes totalling at least 25 cents. (Can’t be just 20 since then you would have a dollar in quarters and half dollars).
Take away pennies, nickels, and dimes until you have 25, 50, 75, or 100 cents left. Add quarters and half dollars as necessary to make change for a dollar.
So $1.19 works, anything greater doesn’t.
Oops, one picky detail, that should have been:
Take away all the quarters and half dollars, leaving pennies, nickels and dimes totalling at least 45 cents. (Can’t be just 40 since then you would have a dollar in quarters and half dollars).
Everything else is fine.