Have you ever noticed that if a teenager has been given $50 to buy a $20 item, no money comes back? Some other item was just so essential...
In this puzzle, we provide the teenager with a good excuse. Artiste and street vendor Claude sells beautiful handmade items for $100 or less but refuses to give change.
You have no cash, but you have three checks. You will make them out in advance to Claude in whole dollar amounts. Your teenager is to give Claude the combination of checks that is the minimum amount more than necessary for the purchase price. For example, if you give your child a $50 check, a $30 check and a $20 check and the item costs $53, your child will give Claude the $50 and $20 checks and Claude will keep the $17 in change in addition to the purchase price.
You like Claude's stuff, but you very much begrudge him his "I keep the change" attitude. So you'd like to minimize the amount he keeps beyond the purchase price.
If you knew that the item in question cost either $20, $40, $50 or $60, which combination of three check amounts could you give in order to leave no change for Claude?
Solution to Warm-up:
$20, $40 and $50 is one of many possible answers.
1. If you did not know how much the purchase price would be except that it is a whole number amount between $1 and $100 inclusive, which amounts would you put on your three checks in order to minimize Claude's change?
2. Suppose Claude publishes his four whole number prices in an advertisement that you see. Can you show how he can guarantee to do so in such a way that at least one item will yield him non-zero change no matter which check amounts you write?
3. This question is open. Again, Claude publishes his four whole-number prices in an advertisement that you see. This time, he not only wants to guarantee to sell at least one item for non-zero change but wants to maximize the amount of change he gets no matter which check amounts you write. Clearly he can't do better than if he has complete freedom as in the first question, but can he do as well?