Difference between revisions of "Mock AIME 2 2006-2007 Problems/Problem 8"
(→Solution) |
m |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | The positive | + | The [[positive integer]]s <math>\displaystyle x_1, x_2, ... , x_7</math> satisfy <math>\displaystyle x_6 = 144</math> and <math>\displaystyle x_{n+3} = x_{n+2}(x_{n+1}+x_n)</math> for <math>\displaystyle n = 1, 2, 3, 4</math>. Find the last three [[digit]]s of <math>\displaystyle x_7</math>. |
==Solution== | ==Solution== | ||
Line 7: | Line 7: | ||
From the givens, <math>x_4 = x_3(x_2 + x_1)</math> and so <math>x_5 = x_4(x_3 + x_2) = x_3(x_2 + x_1)(x_3 + x_2)</math> and <math>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</math>. | From the givens, <math>x_4 = x_3(x_2 + x_1)</math> and so <math>x_5 = x_4(x_3 + x_2) = x_3(x_2 + x_1)(x_3 + x_2)</math> and <math>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</math>. | ||
− | Note that this factorization of 144 contains | + | Note that this factorization of 144 contains a pair of consecutive [[integer]]s, <math>x_2 + x_1</math> and <math>x _2 + x_1 + 1</math>. The [[divisor | factors]] of 144 are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72 and 144 itself. As both <math>x_1</math> and <math>x_2</math> are positive integers, <math>x_1 + x_2 \geq 2</math>, so we must have <math>x_1 + x_2</math> equal to one of 2, 3 and 8. |
If <math>x_1 + x_2 = 2</math> then <math>x_1 = x_2 = 1</math> and so <math>x_3^2(x_3 + 1)\cdot 2 \cdot 3 = 144</math> from which <math>x_3^2(x_3 + 1) = 24</math>. It is clear that this equation has no solutions if <math>x_3 \geq 3</math>, and neither <math>x_3 = 1</math> nor <math>x_3 = 2</math> is a solution, so in this case we have no solutions. | If <math>x_1 + x_2 = 2</math> then <math>x_1 = x_2 = 1</math> and so <math>x_3^2(x_3 + 1)\cdot 2 \cdot 3 = 144</math> from which <math>x_3^2(x_3 + 1) = 24</math>. It is clear that this equation has no solutions if <math>x_3 \geq 3</math>, and neither <math>x_3 = 1</math> nor <math>x_3 = 2</math> is a solution, so in this case we have no solutions. | ||
− | If <math>x_1 + x_2 = 8</math> then <math>x_3^2(x_3 + x_2)\cdot 8 \cdot 9 = 144</math> so <math>x_3^2(x_3 + x_2) = 2</math>. It is clear that <math>x_3 = x_2 = 1</math> is the unique solution to this equation in positive integers. Then <math>x_1 = 8 - x_2 = 7</math> and our sequence is <math>7, 1, 1, 8, 16, 144, 144(16 + 8) = 3456</math>. | + | If <math>x_1 + x_2 = 8</math> then <math>x_3^2(x_3 + x_2)\cdot 8 \cdot 9 = 144</math> so <math>x_3^2(x_3 + x_2) = 2</math>. It is clear that <math>x_3 = x_2 = 1</math> is the unique solution to this equation in positive integers. Then <math>x_1 = 8 - x_2 = 7</math> and our [[sequence]] is <math>7, 1, 1, 8, 16, 144, 144(16 + 8) = 3456</math>. |
If <math>x_1 + x_2 = 3</math> then either: | If <math>x_1 + x_2 = 3</math> then either: |
Revision as of 21:12, 17 September 2006
Problem
The positive integers satisfy
and
for
. Find the last three digits of
.
Solution
This solution is rather long and unpleasant, so a nicer solution may exist:
From the givens, and so
and
.
Note that this factorization of 144 contains a pair of consecutive integers, and
. The factors of 144 are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72 and 144 itself. As both
and
are positive integers,
, so we must have
equal to one of 2, 3 and 8.
If then
and so
from which
. It is clear that this equation has no solutions if
, and neither
nor
is a solution, so in this case we have no solutions.
If then
so
. It is clear that
is the unique solution to this equation in positive integers. Then
and our sequence is
.
If then either:
a) and so
so
, which has no solutions in positive integers
or
b) and so
so
which has solution
. Then our sequence becomes
.
Thus we see there are two possible sequences, but in both cases the answer is 456.