Difference between revisions of "2015 AIME I Problems/Problem 9"

Revision as of 17:22, 22 March 2015

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

@@ Line 8: / Line 8: @@
 Therefore, if either <math>|y-x|</math> or <math>|z-y|</math> 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 <math>|y-x|</math>>1, and <math>|z-y|</math>>1. Then, <math>a_4</math>>=2z, <math>a_5</math>>=4z, and <math>a_6</math>>=4z.
+To prove, let <math>|y-x|>1</math>, and <math>|z-y|>1</math>. Then, <math>a_4 \ge 2z</math>, <math>a_5 \ge 4z</math>, and <math>a_6 \ge 4z</math>.
 However, since the minimum values of <math>a_5</math> and <math>a_6</math> 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, <math>|y-x|</math>=2. Again assume that any other scenario will not meet criteria.
 To prove, divide the other scenarios into two cases: z>1, <math>|y-x|</math>>1, and <math>|z-y|</math>>1; and z=1, <math>|y-x|</math>>2, and <math>|z-y|</math>>1.

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

Difference between revisions of "2015 AIME I Problems/Problem 9"

Revision as of 17:22, 22 March 2015

Problem

Solution

See Also