Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 2 2006-2007 Problems/Problem 8"

(→‎Problem)
(→‎Solution)
 
(12 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
The positive integers <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 digits of <math>x_7</math>.
+
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 23:33, 9 August 2019

Problem

The positive integers $x_1, x_2, ... , x_7$ satisfy $x_6 = 144$ and $x_{n+3} = x_{n+2}(x_{n+1}+x_n)$ for $n = 1, 2, 3, 4$. Find the last three digits of $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$.

Thus we see there are two possible sequences, but in both cases the answer is $\boxed{456}$.


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 $144$ to be $x_5$ and $x_6$ We can also infer that $x_5$ will likely need to be one of the smaller factors.

The factors of $144$ are: $1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144$

Selecting numbers from this list and trying them out, we can satisfy the conditions with these numbers:

$x_5 = 18, x_4 = 6, x_3 = 2, x_2 = 1, x_1 = 2$

So, $x_7 = x_6(x_5 + x_4)$

$x_7 = 144(18 + 6)$

$x_7 = 3456$

Therefore, the answer is $\Rightarrow{\boxed{456}}$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2006-2007_Problems/Problem_8&oldid=108663"