2015 AIME I Problems/Problem 9

Revision as of 18:05, 10 May 2015 by Dibjuv (talk | contribs) (Solution)


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$.


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 \ge 2z$, $a_5 \ge 4z$, and $a_6 \ge 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$ \ge 2z, $a_5$ \ge 4z, $a_6$ \ge 8z, and $a_7$ \ge 16z, by which point we see that this function diverges. For the second one, $a_4 \ge 3$, $a_5 \ge 6$, $a_6 \ge 18$, and $a_7 \ge 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. (16 options, 2 of which coincide with either option 1 or option 2) Adding the total number of such ordered triples yields $280+280-80+16-2=494$.

See Also

2015 AIME I (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS