Difference between revisions of "Mock AIME 2 2006-2007 Problems/Problem 8"
(→Solution) |
|||
(13 intermediate revisions by 7 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== | ||
+ | |||
+ | 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 |