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 be the set of all ordered triple of integers
with
. Each ordered triple in
generates a sequence according to the rule
for all
. Find the number of such sequences for which
for some
.
Solution
Let . First note that if any absolute value equals 0, then
=0.
Also note that if at any position,
, then
.
Then, if any absolute value equals 1, then
=0.
Therefore, if either
or
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
>1, and
>1. Then,
>=2z,
>=4z, and
>=4z.
However, since the minimum values of
and
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,
=2. Again assume that any other scenario will not meet criteria.
To prove, divide the other scenarios into two cases: z>1,
>1, and
>1; and z=1,
>2, and
>1.
For the first one,
>=2z,
>=4z,
>=8z, and
>=16z, by which point we see that this function diverges.
For the second one,
>=3,
>=6,
>=18, and
>=54, by which point we see that this function diverges.
Therefore, the only scenarios where
=0 is when any of the following are met:
<2 (280 options)
<2 (280 options, 80 of which coincide with option 1)
z=1,
=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.