Bassanio has three red coins, four yellow coins, and five blue coins. At any point, he may give Shylock any two coins of different colors in exchange for one coin of the other color; for example, he may give Shylock one red coin and one blue coin, and receive one yellow coin in return. Bassanio wishes to end with coins that are all the same color, and he wishes to do this while having as many coins as possible. How many coins will he end up with, and what color will they be?
Problem 1380
Official solution
Solution:
Let denote the numbers of red, yellow, and blue coins respectively. Note that each of the three possible exchanges do not change the parities of , , or , and eventually one of these differences becomes zero. Since is the only one of these differences that is originally even, it must be the one that becomes zero, and so Bassanio will end with some number of yellow coins. Furthermore, Bassanio loses a coin in each exchange, and he requires at least five exchanges to rid himself of the blue coins, so he will have at most yellow coins at the end of his trading.
It remains to construct a sequence of trades that result in seven yellow coins. First, Bassanio will exchange one yellow and one blue coin for one red coin, leaving him with four red coins, three yellow coins, and four blue coins. He then converts the red and blue coins into yellow coins, resulting in 7 yellow coins, as desired.