Mock AIME 2 2006-2007/Problem 8

From AoPSWiki

Problem

The positive integers $\displaystyle x_1, x_2, ... , x_7$ satisfy $\displaystyle x_6 = 144$ and $\displaystyle x_{n+3} = x_{n+2}(x_{n+1}+x_n)$ for $\displaystyle n = 1, 2, 3, 4$ . Find the last three digits of $\displaystyle x_7$ .

Solution

This solution is rather long and unpleasant, so a nicer solution may exist:

From the givens, $x_4 = x_3(x_2 + x_1)$ and so $x_5 = x_4(x_3 + x_2) = x_3(x_2 + x_1)(x_3 + x_2)$ and $x_6 = x_5(x_4 + x_3) = x_3(x_2 + x_1)(x_3 + x_2)(x_3(x_2 + x_1) + x_3) = x_3^2(x_3 + x_2)(x_2 + x_1)(x_2 + x_1 + 1) = 144 = 2^4\cdot 3^2$ .

Note that this factorization of 144 contains a pair of consecutive integers, $x_2 + x_1$ and $x _2 + x_1 + 1$ . The factors of 144 are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72 and 144 itself. As both $x_1$ and $x_2$ are positive integers, $x_1 + x_2 \geq 2$ , so we must have $x_1 + x_2$ equal to one of 2, 3 and 8.

If $x_1 + x_2 = 2$ then $x_1 = x_2 = 1$ and so $x_3^2(x_3 + 1)\cdot 2 \cdot 3 = 144$ from which $x_3^2(x_3 + 1) = 24$ . It is clear that this equation has no solutions if $x_3 \geq 3$ , and neither $x_3 = 1$ nor $x_3 = 2$ is a solution, so in this case we have no solutions.

If $x_1 + x_2 = 8$ then $x_3^2(x_3 + x_2)\cdot 8 \cdot 9 = 144$ so $x_3^2(x_3 + x_2) = 2$ . It is clear that $x_3 = x_2 = 1$ is the unique solution to this equation in positive integers. Then $x_1 = 8 - x_2 = 7$ and our sequence is $7, 1, 1, 8, 16, 144, 144(16 + 8) = 3456$ .

If $x_1 + x_2 = 3$ then either:

a) $x_1 = 1, x_2 = 2$ and so $x_3^2(x_3 + 2)\cdot 3\cdot 4 = 144$ so $x_3^2(x_3 + 2) = 12$ , which has no solutions in positive integers

or

b) $x_1 = 2, x_2 = 1$ and so $x_3^2(x_3 + 1)\cdot 3\cdot 4 = 144$ so $x_3^2(x_3 + 1) = 12$ which has solution $x_3 = 2$ . Then our sequence becomes $2, 1, 2, 6, 18, 144, 144(18 + 6) = 3456$ .