I went camping this past weekend (my first time) and my neighbor (who’s actually my neighbor in real life and was my neighbor at the camp site) was drinking a Snapple and read the following fact back to me:
Snapple Real Fact #804: There are 293 ways to make change for a dollar.
My first reaction was “Mmm…interesting”, but I couldn’t help wondering whether the Snapple folks did their math correctly. So after I got home and unpacked the car, I wrote a little Constraint Programming code in Comet to check this fact. It turns out that the number is indeed 293 if the following two things are allowed: (i) returning a 1-dollar coin in exchange for a dollar bill, and (ii) using half-dollar coins which, in my opinion, are rare these days. Here’s a list of the 292 ways that do not include using a 1-dollar coin which, in my opinion, isn’t really “giving change”.
If you’re wondering how many ways there are when you’re not allowed to use 1-dollar or half-dollar coins, the answer is 242. Here’s a list of all such possible ways.
Update: A friend asked me what the number would be if we considered the quarters from each of the 50 states as a different coin. In that case the number of possible ways increases to 515,184 (including the 1-dollar coin).