Difference between revisions of "Mock AIME 2 2006-2007 Problems/Problem 8"
m |
(→Solution) |
||
(10 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | The positive | + | The [[positive integer]]s <math>x_1, x_2, ... , x_7</math> satisfy <math>x_6 = 144</math> and <math>x_{n+3} = x_{n+2}(x_{n+1}+x_n)</math> for <math>n = 1, 2, 3, 4</math>. Find the last three [[digit]]s of <math>x_7</math>. |
==Solution== | ==Solution== | ||
− | |||
− | + | This solution is rather long and unpleasant, so a nicer solution may exist: | |
− | + | 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 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 = 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: | ||
+ | |||
+ | a) <math>x_1 = 1, x_2 = 2</math> and so <math>x_3^2(x_3 + 2)\cdot 3\cdot 4 = 144</math> so <math>x_3^2(x_3 + 2) = 12</math>, which has no solutions in positive integers | ||
+ | |||
+ | or | ||
+ | |||
+ | b) <math>x_1 = 2, x_2 = 1</math> and so <math>x_3^2(x_3 + 1)\cdot 3\cdot 4 = 144</math> so <math>x_3^2(x_3 + 1) = 12</math> which has solution <math>x_3 = 2</math>. Then our sequence becomes <math>2, 1, 2, 6, 18, 144, 144(18 + 6) = 3456</math>. | ||
+ | |||
+ | Thus we see there are two possible sequences, but in both cases the answer is <math>\boxed{456}</math>. | ||
+ | |||
+ | |||
+ | |||
+ | A Second Simpler Solution: | ||
+ | |||
+ | We can use smart "guess-and-check" for this problem, seeing as there are not that many options anyways. We know that we need factors of <math>144</math> to be <math>x_5</math> and <math>x_6</math> We can also infer that <math>x_5</math> will likely need to be one of the smaller factors. | ||
+ | |||
+ | The factors of <math>144</math> are: <math>1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144</math> | ||
+ | |||
+ | Selecting numbers from this list and trying them out, we can satisfy the conditions with these numbers: | ||
+ | |||
+ | <math>x_5 = 18, x_4 = 6, x_3 = 2, x_2 = 1, x_1 = 2</math> | ||
+ | |||
+ | So, <math>x_7 = x_6(x_5 + x_4)</math> | ||
+ | |||
+ | <math>x_7 = 144(18 + 6)</math> | ||
+ | |||
+ | <math>x_7 = 3456</math> | ||
+ | |||
+ | Therefore, the answer is <math>\Rightarrow{\boxed{456}}</math> | ||
+ | |||
+ | ==See Also== | ||
+ | {{Mock AIME box|year=2006-2007|n=2|num-b=7|num-a=9}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 00:33, 10 August 2019
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 .
A Second Simpler Solution:
We can use smart "guess-and-check" for this problem, seeing as there are not that many options anyways. We know that we need factors of to be
and
We can also infer that
will likely need to be one of the smaller factors.
The factors of are:
Selecting numbers from this list and trying them out, we can satisfy the conditions with these numbers:
So,
Therefore, the answer is
See Also
Mock AIME 2 2006-2007 (Problems, Source) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 |