Library / Harvard-MIT Mathematics Tournament /307 of 352

Harvard-MIT Mathematics Tournament

Algebra Difficulty 5.7 AIME, harder Prove it United States

Problem:

Steph and Jeff each start with the number $4$ , and Travis is flipping a coin. Every time he flips a heads, Steph replaces her number $x$ with $2x-1$ , and Jeff replaces his number $y$ with $y+8$ . Every time he flips a tails, Steph replaces her number $x$ with $\frac{x+1}{2}$ , and Jeff replaces his number $y$ with $y-3$ . After some (positive) number of coin flips, Steph and Jeff miraculously end up with the same number below $2012$ . How many times was the coin flipped?

Solution

Solution:

Answer: $137$

Suppose that $a$ heads and $b$ tails are flipped. Jeff's number at the end is $4 + 8a - 3b$ . Note that the operations which Steph applies are inverses of each other, and as a result it is not difficult to check by induction that her final number is simply $1 + 3 \cdot 2^{a-b}$ .

We now have $4 + 8a - 3b = 1 + 3 \cdot 2^{a-b}$ . Letting $n = a-b$ , we see that $2^n - n - 1$ must be divisible by $5$ , so that $a$ is an integer. In particular, $n$ is a positive integer. Furthermore, we have $1 + 3 \cdot 2^n < 2012$ , so that $n \leq 9$ . We see that the only possibility is for $n = 7 = a-b$ , and thus $4 + 8a - 3b = 385$ . Solving, we get $a = 72$ , $b = 65$ , so our answer is $72 + 65 = 137$ .

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

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