Maths Olympiad Prep

Library / /23 of 25

Combinatorics Difficulty 4.7 AIME Prove it Japan

Suppose a magician can perform each of the following 3 kinds of tricks any number of times:
* Trick A: Change 1 orange and 1 grape into 2 apples.
* Trick B: Change 1 grape and 1 apple into 3 oranges
* Trick C: Change 1 apple and 1 orange into 4 grapes.

Initially, there were 2011 each of apples, grapes and oranges, and the magician performed a number of tricks and ended up with the situation in which there are 2011 apples, 2011 grapes and more than 2011 oranges. What is the smallest possible number of oranges in this situation?

Solution

The number of apples decreases by 11 after 11 trick of type BB or CC is performed, and increases by 22 after 11 trick of type AA is performed. The number of grapes decreases by 11 after 11 trick of type AA or BB is performed, and increases by 44 after 11 trick of type CC is performed. Suppose the magician used xx tricks of type AA, yy tricks of type BB and zz tricks of type CC to reach the situation where the numbers of apples and grapes are the same as their initial numbers, then we must have
y+z=2x,x+y=4z. y+z=2x, \quad x+y=4z.
Since x,y,zx, y, z are non-negative integers and at least one of x,y,zx, y, z must be positive, we see that the solution of the simultaneous equation above must have the form (x,y,z)=(5k,7k,3k)(x, y, z) = (5k, 7k, 3k), where kk is a positive integer. Since the number of oranges decreases by 11 after 11 trick of type AA or CC is performed and increases by 33 after 11 trick of type BB is performed, the change of the number of oranges after 5k5k tricks of type AA, 7k7k tricks of type BB and 3k3k tricks of type CC are performed is given by 5k+3×7k3k=13k-5k+3 \times 7k-3k = 13k. k=1k=1, then, gives the smallest possible number of oranges when the number is 20112011 for both apples and grapes, which is 2011+13=20242011+13=2024.

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.