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 "2015 AIME I Problems/Problem 9"

(Created page with "==Problem== Let <math>S</math> be the set of all ordered triple of integers <math>(a_1,a_2,a_3)</math> with <math>1 \le a_1,a_2,a_3 \le 10</math>. Each ordered triple in <math...")
 
(→‎Problem)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Let <math>S</math> be the set of all ordered triple of integers <math>(a_1,a_2,a_3)</math> with <math>1 \le a_1,a_2,a_3 \le 10</math>. Each ordered triple in <math>S</math> generates a sequence according to the rule <math>a_n=a_{n-1}\cdot | a_{n-2}-a_{n-3} |</math> for all <math>n\ge 4</math>. Find the number of such sequences for which <math>a_n=0</math> for some <math>n</math>.
 
Let <math>S</math> be the set of all ordered triple of integers <math>(a_1,a_2,a_3)</math> with <math>1 \le a_1,a_2,a_3 \le 10</math>. Each ordered triple in <math>S</math> generates a sequence according to the rule <math>a_n=a_{n-1}\cdot | a_{n-2}-a_{n-3} |</math> for all <math>n\ge 4</math>. Find the number of such sequences for which <math>a_n=0</math> for some <math>n</math>.
 +
 +
==Solution==
 +
Let <math>a_1=x, a_2=y, a_3=z</math>. First note that if any absolute value equals 0, then <math>a_n</math>=0.
 +
Also note that if at any position, <math>a_n=a_n-1</math>, then <math>a_n+2=0</math>.
 +
Then, if any absolute value equals 1, then <math>a_n</math>=0.
 +
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.
 +
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.
 +
For the first one, <math>a_4</math>>=2z, <math>a_5</math>>=4z, <math>a_6</math>>=8z, and <math>a_7</math>>=16z, by which point we see that this function diverges.
 +
For the second one, <math>a_4</math>>=3, <math>a_5</math>>=6, <math>a_6</math>>=18, and <math>a_7</math>>=54, by which point we see that this function diverges.
 +
Therefore, the only scenarios where <math>a_n</math>=0 is when any of the following are met:
 +
<math>|y-x|</math><2 (280 options)
 +
<math>|z-y|</math><2 (280 options, 80 of which coincide with option 1)
 +
z=1, <math>|y-x|</math>=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.
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2015|n=I|num-b=8|num-a=10}}
 
{{AIME box|year=2015|n=I|num-b=8|num-a=10}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 14:31, 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$>=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.

See Also

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_AIME_I_Problems/Problem_9&oldid=69400"