Problem:
You are traveling in a foreign country whose currency consists of five different-looking kinds of coins. You have several of each coin in your pocket. You remember that the coins are worth , , , , and florins, but you have no idea which coin is which and you don't speak the local language. You find a vending machine where a single candy can be bought for florin: you insert any kind of coin, and receive
candy plus any change owed. You can only buy one candy at a time, but you can buy as many as you want, one after the other.
What is the least number of candies that you must buy to ensure that you can determine the values of all the coins? Prove that your answer is correct.
Solution
Solution:
The answer is four.
First we show that three candies are not always enough. If you only buy three candies, then it is possible the three coins you spend will be some combination of -, -, and -florin coins, in which case you definitely won't receive any - or -florin coins in change. Thus, in this situation, you do not get any information that can be used to distinguish the - and -florin coins.
Now we show that four candies are enough. In each of these transactions, pay with a different kind of coin. If any of the transactions does not produce change, then you must have paid in that transaction with a -florin coin. If all the transactions produce change, then the coin you didn't use as payment is the -florin coin. In either case, you can identify the -florin coin. Since the change for florins will be florin, you can now tell if you paid for any of the transactions with a -florin coin, and thereby identify which of the five coins has a value of florins. Next, we know that the change for florins will be either two -florin coins or four -florin coins, or one -florin and two -florin coins; in any event, you can recognize these collections of coins and then deduce which coin is the -florin coin (if you see one of these collections, then you know which coin was the -florin coin; otherwise, you know it was the coin you didn't use as payment). Likewise, change for florins will be a collection of coins that total florins, and all such collections can now be recognized. Thus we can deduce which coin is the -florin coin, and finally we can apply the same procedure to deduce the identity of the -florin coin.