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"

m (→‎Solution 2)
m
 
(6 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
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==
+
==Solution 1==
 
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=0</math>.
 
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=0</math>.
 
Also note that if at any position, <math>a_n=a_{n-1}</math>, then <math>a_{n+2}=0</math>.
 
Also note that if at any position, <math>a_n=a_{n-1}</math>, then <math>a_{n+2}=0</math>.
Line 24: Line 24:
  
 
Because <math>a_4 \ge 2z</math>, <math>a_5 \ge 4z</math>, <math>a_6 \ge 8z</math>, and <math>a_7 \ge 16z</math> doesn't mean the function diverges. What if <math>z = 7</math>, <math>a_4 = 60</math>, and <math>a_5 = 30</math> too?
 
Because <math>a_4 \ge 2z</math>, <math>a_5 \ge 4z</math>, <math>a_6 \ge 8z</math>, and <math>a_7 \ge 16z</math> doesn't mean the function diverges. What if <math>z = 7</math>, <math>a_4 = 60</math>, and <math>a_5 = 30</math> too?
 +
 +
*Note to the Note to author:
 +
 +
This isn't possible because the difference between is either 0, 1, or some number greater than 1. If <math>a_4 = 63</math> (since it must be a multiple of <math>z</math>), then a_5 is either 0, 63, or some number greater than 63.
  
 
==Solution 2==
 
==Solution 2==
 
Note that the only way for a <math>0</math> to be produced at <math>a_n</math> is if either <math>a_{n-1} = 0</math> or <math>a_{n-2} = a_{n-3}</math>. Since the first one will eventually get to the first three assuming that there is no <math>a_{n-2} = a_{n-3}</math> for any <math>n</math>, that is not possible because <math>a_1 , a_2 , a_3 >= 1</math>. Therefore, we need <math>a_{n - 2} = a_{n - 3}</math>.  
 
Note that the only way for a <math>0</math> to be produced at <math>a_n</math> is if either <math>a_{n-1} = 0</math> or <math>a_{n-2} = a_{n-3}</math>. Since the first one will eventually get to the first three assuming that there is no <math>a_{n-2} = a_{n-3}</math> for any <math>n</math>, that is not possible because <math>a_1 , a_2 , a_3 >= 1</math>. Therefore, we need <math>a_{n - 2} = a_{n - 3}</math>.  
  
−
If <math>2</math> consecutive numbers out of <math>a_1 , a_2 , a_3</math> are equal, then those cases work(<math>a_1</math> and <math>a_2</math> or <math>a_2</math> and <math>a_3</math> <math>[b]NOT[/b]</math> <math>a_1</math> and <math>a_3</math>). This is simply <math>10 \cdot 10 + 10 \cdot 10 - 10 = 190</math> by PIE.  
+
If <math>2</math> consecutive numbers out of <math>a_1 , a_2 , a_3</math> are equal, then those cases work(<math>a_1</math> and <math>a_2</math> or <math>a_2</math> and <math>a_3</math> <math>\textbf{NOT}</math> <math>a_1</math> and <math>a_3</math>). This is simply <math>10 \cdot 10 + 10 \cdot 10 - 10 = 190</math> by PIE.  
  
 
Now, note that if any of the first three numbers have difference of <math>1</math>, we have another working case. First, we calculate how many there are given exactly one of <math>a_1,a_2</math> or <math>a_2,a_3</math> have difference <math>1</math>. Given <math>3</math> numbers such that the first <math>2</math> have difference <math>1</math>, exactly <math>4</math> permutations work(assuming the numbers are <math>x,y,</math> and <math>z</math> such that <math>|x-y| = 1</math>): <math>x,y,z</math>; <math>y,x,z</math>; <math>z,x,y</math>; and <math>z,y,x</math>. If the two consecutive numbers are <math>1</math> and <math>2</math>, then the last number has <math>7</math> possiblities: <math>4,5,6,\cdots , 10</math>. This is symmetric for <math>9</math> and <math>10</math>. If the consecutive numbers are <math>(2,3),\cdots , (8,9)</math>, there are <math>6</math> possibilities(<math>10</math> minus the numbers themselves and the numbers directly above and below). Note that we are not counting any cases already counted in the first case. Therefore, this case gives you <math>4(7 + 6 * 7 + 7) = 224</math>. Now we consider the case that there both adjacent <math>a</math>s have increments of <math>1</math>. <cmath>+1 , +1 \rightarrow 8</cmath> <cmath>-1 , -1 \rightarrow 8</cmath> <cmath>+1 , -1 \rightarrow 9</cmath> <cmath>-1 , +1 \rightarrow 9</cmath> Therefore this gives <math>224 + 8 + 8 + 9 + 9 = 258</math>. However, note that we have to add the case where you have <math>3</math> consecutive numbers in arrangement such that only <math>2</math> consecutive numbers have difference <math>1</math>. For example, <math>1,3,2</math> is one such triple. There are <math>8</math> triples of consecutive numbers and <math>4</math> ways to arrange each one(e.x: <math>(1,3,2);(3,1,2);(2,1,3);(2,3,1)</math>). This adds on 32 working cases, so this case gives <math>258 + 32 = 290</math>.
 
Now, note that if any of the first three numbers have difference of <math>1</math>, we have another working case. First, we calculate how many there are given exactly one of <math>a_1,a_2</math> or <math>a_2,a_3</math> have difference <math>1</math>. Given <math>3</math> numbers such that the first <math>2</math> have difference <math>1</math>, exactly <math>4</math> permutations work(assuming the numbers are <math>x,y,</math> and <math>z</math> such that <math>|x-y| = 1</math>): <math>x,y,z</math>; <math>y,x,z</math>; <math>z,x,y</math>; and <math>z,y,x</math>. If the two consecutive numbers are <math>1</math> and <math>2</math>, then the last number has <math>7</math> possiblities: <math>4,5,6,\cdots , 10</math>. This is symmetric for <math>9</math> and <math>10</math>. If the consecutive numbers are <math>(2,3),\cdots , (8,9)</math>, there are <math>6</math> possibilities(<math>10</math> minus the numbers themselves and the numbers directly above and below). Note that we are not counting any cases already counted in the first case. Therefore, this case gives you <math>4(7 + 6 * 7 + 7) = 224</math>. Now we consider the case that there both adjacent <math>a</math>s have increments of <math>1</math>. <cmath>+1 , +1 \rightarrow 8</cmath> <cmath>-1 , -1 \rightarrow 8</cmath> <cmath>+1 , -1 \rightarrow 9</cmath> <cmath>-1 , +1 \rightarrow 9</cmath> Therefore this gives <math>224 + 8 + 8 + 9 + 9 = 258</math>. However, note that we have to add the case where you have <math>3</math> consecutive numbers in arrangement such that only <math>2</math> consecutive numbers have difference <math>1</math>. For example, <math>1,3,2</math> is one such triple. There are <math>8</math> triples of consecutive numbers and <math>4</math> ways to arrange each one(e.x: <math>(1,3,2);(3,1,2);(2,1,3);(2,3,1)</math>). This adds on 32 working cases, so this case gives <math>258 + 32 = 290</math>.
Line 36: Line 40:
 
Therefore, our answer is <math>190 + 290 + 14 = \boxed{494}</math>.
 
Therefore, our answer is <math>190 + 290 + 14 = \boxed{494}</math>.
 
Solution by hyxue
 
Solution by hyxue
 +
 +
 +
==Video Solution==
 +
https://youtu.be/nxieVbkk0jY
 +
 +
~MathProblemSolvingSkills.com
 +
  
 
==See Also==
 
==See Also==

Latest revision as of 19:35, 28 July 2023

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 1

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=\boxed{494}$.

  • Note to author:

Because $a_4 \ge 2z$, $a_5 \ge 4z$, $a_6 \ge 8z$, and $a_7 \ge 16z$ doesn't mean the function diverges. What if $z = 7$, $a_4 = 60$, and $a_5 = 30$ too?

  • Note to the Note to author:

This isn't possible because the difference between is either 0, 1, or some number greater than 1. If $a_4 = 63$ (since it must be a multiple of $z$), then a_5 is either 0, 63, or some number greater than 63.

Solution 2

Note that the only way for a $0$ to be produced at $a_n$ is if either $a_{n-1} = 0$ or $a_{n-2} = a_{n-3}$. Since the first one will eventually get to the first three assuming that there is no $a_{n-2} = a_{n-3}$ for any $n$, that is not possible because $a_1 , a_2 , a_3 >= 1$. Therefore, we need $a_{n - 2} = a_{n - 3}$.

If $2$ consecutive numbers out of $a_1 , a_2 , a_3$ are equal, then those cases work($a_1$ and $a_2$ or $a_2$ and $a_3$ $\textbf{NOT}$ $a_1$ and $a_3$). This is simply $10 \cdot 10 + 10 \cdot 10 - 10 = 190$ by PIE.

Now, note that if any of the first three numbers have difference of $1$, we have another working case. First, we calculate how many there are given exactly one of $a_1,a_2$ or $a_2,a_3$ have difference $1$. Given $3$ numbers such that the first $2$ have difference $1$, exactly $4$ permutations work(assuming the numbers are $x,y,$ and $z$ such that $|x-y| = 1$): $x,y,z$; $y,x,z$; $z,x,y$; and $z,y,x$. If the two consecutive numbers are $1$ and $2$, then the last number has $7$ possiblities: $4,5,6,\cdots , 10$. This is symmetric for $9$ and $10$. If the consecutive numbers are $(2,3),\cdots , (8,9)$, there are $6$ possibilities($10$ minus the numbers themselves and the numbers directly above and below). Note that we are not counting any cases already counted in the first case. Therefore, this case gives you $4(7 + 6 * 7 + 7) = 224$. Now we consider the case that there both adjacent $a$s have increments of $1$. \[+1 , +1 \rightarrow 8\] \[-1 , -1 \rightarrow 8\] \[+1 , -1 \rightarrow 9\] \[-1 , +1 \rightarrow 9\] Therefore this gives $224 + 8 + 8 + 9 + 9 = 258$. However, note that we have to add the case where you have $3$ consecutive numbers in arrangement such that only $2$ consecutive numbers have difference $1$. For example, $1,3,2$ is one such triple. There are $8$ triples of consecutive numbers and $4$ ways to arrange each one(e.x: $(1,3,2);(3,1,2);(2,1,3);(2,3,1)$). This adds on 32 working cases, so this case gives $258 + 32 = 290$.

Note that there is an ultraspecial(Yes, I know that's not a word) case where we generate a pair of $a_i$ that have difference one. This can only happen if $a_3 = 1$ and $a_1$ and $a_2$ have difference $2$. This contributes $14$ cases($2 * 8$ and then subtract $2$ because of the cases $3,1,1$ and $4,2,1$).

Therefore, our answer is $190 + 290 + 14 = \boxed{494}$. Solution by hyxue


Video Solution

https://youtu.be/nxieVbkk0jY

~MathProblemSolvingSkills.com


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=196173"