Maths Olympiad Prep

Library / /61 of 86

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it United States

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 11, 22, 55, 1010, and 2020 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 11 florin: you insert any kind of coin, and receive
11 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 11-, 22-, and 55-florin coins, in which case you definitely won't receive any 1010- or 2020-florin coins in change. Thus, in this situation, you do not get any information that can be used to distinguish the 1010- and 2020-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 11-florin coin. If all the transactions produce change, then the coin you didn't use as payment is the 11-florin coin. In either case, you can identify the 11-florin coin. Since the change for 22 florins will be 11 florin, you can now tell if you paid for any of the transactions with a 22-florin coin, and thereby identify which of the five coins has a value of 22 florins. Next, we know that the change for 55 florins will be either two 22-florin coins or four 11-florin coins, or one 22-florin and two 11-florin coins; in any event, you can recognize these collections of coins and then deduce which coin is the 55-florin coin (if you see one of these collections, then you know which coin was the 55-florin coin; otherwise, you know it was the coin you didn't use as payment). Likewise, change for 1010 florins will be a collection of coins that total 99 florins, and all such collections can now be recognized. Thus we can deduce which coin is the 1010-florin coin, and finally we can apply the same procedure to deduce the identity of the 2020-florin coin.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.