2015 AIME I Problems/Problem 9

Problem

Let $S$ be the set of all ordered triple of integers $(a_1,a_2,a_3)$ with $1 \le a_1,a_2,a_3 \le 10$ . Each ordered triple in $S$ generates a sequence according to the rule $a_n=a_{n-1}\cdot | a_{n-2}-a_{n-3} |$ for all $n\ge 4$ . Find the number of such sequences for which $a_n=0$ for some $n$ .

Solution

Let $a_1=x, a_2=y, a_3=z$ . First note that if any absolute value equals 0, then $a_n$ =0. Also note that if at any position, $a_n=a_{n-1}$ , then $a_{n+2}=0$ . Then, if any absolute value equals 1, then $a_n$ =0. Therefore, if either $|y-x|$ or $|z-y|$ is less than or equal to 1, then that ordered triple meets the criteria. Assume that to be the only way the criteria is met. To prove, let $|y-x|$ >1, and $|z-y|$ >1. Then, $a_4$ >=2z, $a_5$ >=4z, and $a_6$ >=4z. However, since the minimum values of $a_5$ and $a_6$ are equal, there must be a scenario where the criteria was met that does not meet our earlier scenarios. Calculation shows that to be z=1, $|y-x|$ =2. Again assume that any other scenario will not meet criteria. To prove, divide the other scenarios into two cases: z>1, $|y-x|$ >1, and $|z-y|$ >1; and z=1, $|y-x|$ >2, and $|z-y|$ >1. For the first one, $a_4$ >=2z, $a_5$ >=4z, $a_6$ >=8z, and $a_7$ >=16z, by which point we see that this function diverges. For the second one, $a_4$ >=3, $a_5$ >=6, $a_6$ >=18, and $a_7$ >=54, by which point we see that this function diverges. Therefore, the only scenarios where $a_n$ =0 is when any of the following are met: $|y-x|$ <2 (280 options) $|z-y|$ <2 (280 options, 80 of which coincide with option 1) z=1, $|y-x|$ =2. (14 options, none of which coincide with either option 1 or option 2) Adding the total number of such ordered triples yields 280+280-80+14=494.

2015 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 8	Followed by Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2015 AIME I Problems/Problem 9

Problem

Solution

See Also