Solution to Problem 10: "A Change for the Bettor"

(A) If you had 1-$50, 4-$20, 1-$5, and 4-$2, then you have a total of $143 without being able to make change for $100.

Let's assume that it was possible to have more than $143 in bills and still not be able to make change for $100.  Since it is possible [sic], choose from among all possibilities one with a minimal number of bills.  (Therefore, for instance, there aren't more than two $10 in this solution, because we could "trade them in" for a $20 and have another solution with fewer bills.)  There cannot be more than one $50, four $20, one $10, one $5, four $2, and one $1 in the set, which makes a total of $154.  If we removed a $50 or a $20 from this maximum value, then the total would drop below $143, so we know that there is a $50 and four $20 in this solution.  There can't be a $10, then, because 50+20+20+10 would be change.  This brings the total down to $144, so we cannot go any lower.  But 50+20+20+5+2+2+1 is change for $100.   Therefore, our assumption that some collection of more than $143 would not be able to make change for $100 was in error.

(B) If there were a coin in that universe that was not a factor of 60, then any number of a coin of that value would not be sufficient to make change for a dollar, but we are told that any value over 133 cents can make change.  Therefore, the only candidates for coins are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30.

We'd like to exagerate the situation in problem A with out fantasy currencies by having as large a quantity of each individual coin as possible and not have those coins work with each other to make change.  So having two coins such that one is a multiple of the other would not be advantageous to having a large total (as in problem A where we wound up not using 10's and 1's at all in our maximum collection). 

Let's consider A=12, B=15, C=20; three large values that are not multiples of each other in any way.  You can have as many as 4 A's (48 cents), 3 B's (45 cents), and 2 C's (40 cents - total of 133 cents) individually before making change for a dollar.   Can a more exotic combination of those nine coins make change?  No.  If you had any number of A's, then the sum would not be a multiple of 5.  And if you had any number of B's, then the sum would not be a multiple of 4.  Finally, if you had any number of C's, then the number would not be a multiple of 3.  Therefore, 4 A's, 3 B's and 2 C's do not make change for a dollar.  However, any set of coins that totalled more must have either at least 5 A's, 4 B's, or 3 C's, so you could make change for a dollar using just one type of coin.

Therefore, the solution to A is 143 and the solution to B is 12 15 20.

Comments: I answered part (A) quickly, but got it wrong.  (I had two $20's instead of four for a total of $103).  I didn't even try part (B).  Given that it was only 10 points, I don't think it would have been worth it for me.