Browse · MathNet
PrintJapan Mathematical Olympiad
Japan counting and probability
Problem
Currently circulating coins in Japanese currency come in 6 different denominations: 500 yen, 100 yen, 50 yen, 10 yen, 5 yen and 1 yen. Taro had 1 each of 1000 yen note, 100 yen coin, 10 yen coin and 1 yen coin. He made a certain purchase from a merchant and handed him all he had and received some change. Assume that Taro made the payment in such a way that he would not receive in the change any coins of the denominations same as what he had had to begin with, nor a 1000 yen note. Furthermore, he chose the method of the payment so that he would end up with the minimum possible number of coins when he received his change. Assume also that the merchant gave Taro the change with minimum possible number of coins. Count the case of no change as a possibility for the purchase price also. Under these conditions how many distinct purchase prices are possible?
Solution
To begin with, we note that two or more of 500 yen coins, or of 50 yen coins, or of 5 yen coins could not be included in the change Taro received. This is because if two or more of any of these coins were in the change, two of them could be exchanged for one 1000 yen note, or one 100 yen coin or one 10 yen coin to reduce the total number of coins in the change. Also, the change did
not include 1000 yen note, 100 yen coin, 10 yen coin or 1 yen coin, since Taro used all of these in his payment. Therefore, the change must have consisted of zero or one piece each of 500 yen, 50 yen and 5 yen coins. Consequently, the purchase price must have been of the form: yen, where each of , , being either 0 or 1.
Conversely, let us show that if the purchase price is of the form yen, with each one of , , being 0 or 1, then Taro would make his payment in the way specified in the statement of the problem. Note that as each of , , is either 0 or 1, a 500 yen, b 50 yen and c 5 yen coins together would yield the method of payment of yen with the minimum number of coins. The change does not contain any of 1000 yen note or 100 yen, 10 yen, 1 yen coins, as we have noted before. Also, the amount of change should be yen regardless of the method of payment, and hence the number of coins Taro received as the change is the minimum possible for the amount of change.
Since each of , , can take either 0 or 1, the number of possible values for the purchase price is .
not include 1000 yen note, 100 yen coin, 10 yen coin or 1 yen coin, since Taro used all of these in his payment. Therefore, the change must have consisted of zero or one piece each of 500 yen, 50 yen and 5 yen coins. Consequently, the purchase price must have been of the form: yen, where each of , , being either 0 or 1.
Conversely, let us show that if the purchase price is of the form yen, with each one of , , being 0 or 1, then Taro would make his payment in the way specified in the statement of the problem. Note that as each of , , is either 0 or 1, a 500 yen, b 50 yen and c 5 yen coins together would yield the method of payment of yen with the minimum number of coins. The change does not contain any of 1000 yen note or 100 yen, 10 yen, 1 yen coins, as we have noted before. Also, the amount of change should be yen regardless of the method of payment, and hence the number of coins Taro received as the change is the minimum possible for the amount of change.
Since each of , , can take either 0 or 1, the number of possible values for the purchase price is .
Final answer
8
Techniques
Games / greedy algorithmsIntegers