Maths Olympiad Prep

Library / /36 of 39

, 2012

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Belarus

Pirate Bob has 14 silver, 15 gold, and 16 platinum coins, and Pirate Bill has 16 silver, 15 gold, and 14 platinum coins. From time to time they exchange their coins using the following rule: one of the pirates gives to the other pirate two coins of the same metal and instead of them gets two coins from the other two metals. At some moment Bill has no gold coins.
How many platinum coins can Bill have at this moment?

Solution

Let (S,G,P)(S, G, P) be the set of gold, silver and platinum coins of Bill at some moment. The initial set is (16,15,14)(16, 15, 14). Note that Bob and Bill have together 3030 gold, 3030 silver and 3030 platinum coins. So, S30S \le 30, G30G \le 30, and P30P \le 30 at any moment. By condition, S+G+P=16+15+14=45S + G + P = 16 + 15 + 14 = 45 at any time. Therefore, if G=0G = 0 at some moment, then P=45S4530=15P = 45 - S \ge 45 - 30 = 15 at the same moment, so 15P3015 \le P \le 30.

By condition, after any interchange of coins the set (S,G,P)(S, G, P) can be one of the following sets
1) (S+2,G1,P1)(S+2, G-1, P-1),
2) (S2,G+1,P+1)(S-2, G+1, P+1),
3) (S1,G+2,P1)(S-1, G+2, P-1),
4) (S+1,G2,P+1)(S+1, G-2, P+1),
5) (S1,G1,P+2)(S-1, G-1, P+2),
6) (S+1,G+1,P2)(S+1, G+1, P-2).
It is easy to see that the difference GPG - P in the old and in any new set are congruent modulo 33 in any case. We have GP=1514=1G - P = 15 - 14 = 1 for the initial set, so GP1(mod3)G - P \equiv 1 \pmod 3 at any time. For G=0G = 0 we have P2(mod3)P \equiv 2 \pmod 3. We see that the numbers 17,20,23,26,17, 20, 23, 26, and 2929 are congruent 22 modulo 33 (among the numbers from 1515 to 3030). Therefore, when Bill has 00 gold coins he can have only one of these five values of platinum coins. On the other hand, Bill can have any of these five numbers of platinum coins.

Indeed, if Bill gives two gold coins to Bill seven times successively, then (16,15,14)(23,1,21)(16, 15, 14) \rightarrow (23, 1, 21). The first table shows how Bill can get the smallest number of platinum coins (1717), and the second table shows how Bill can get the greatest number of platinum coins (2929). We also see that Bill can also get 20,23,2620, 23, 26 coins.

| SS | 23 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |
|-----|----|----|----|----|----|----|----|----|----|
| GG | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
| PP | 21 | 22 | 23 | 21 | 19 | 20 | 18 | 16 | 17 |

| SS | 23 | 21 | 22 | 20 | 18 | 19 | 17 | 15 | 16 |
|-----|----|----|----|----|----|----|----|----|----|
| GG | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
| PP | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |

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 and solution reproduced as published; topic and difficulty added by this site.