Difference between revisions of "2014 AIME II Problems/Problem 15"
m |
|||
(18 intermediate revisions by 8 users not shown) | |||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | Note that | + | Note that for any <math>x_i</math>, for any prime <math>p</math>, <math>p^2 \nmid x_i</math>. This provides motivation to translate <math>x_i</math> into a binary sequence <math>y_i</math>. |
+ | |||
+ | Let the prime factorization of <math>x_i</math> be written as <math>p_{a_1} \cdot p_{a_2} \cdot p_{a_3} \cdots</math>, where <math>p_i</math> is the <math>i</math>th prime number. Then, for every <math>p_{a_k}</math> in the prime factorization of <math>x_i</math>, place a <math>1</math> in the <math>a_k</math>th digit of <math>y_i</math>. This will result in the conversion <math>x_1 = 2, x_{2} = 3, x_{3} = 2 * 3 = 6, \cdots</math>. | ||
+ | |||
+ | Multiplication for the sequence <math>x_i</math> will translate to addition for the sequence <math>y_i</math>. Thus, we see that <math>x_{n+1}X(x_n) = x_np(x_n)</math> translates into <math>y_{n+1} = y_n+1</math>. Since <math>x_0=1</math>, and <math>y_0=0</math>, <math>x_i</math> corresponds to <math>y_i</math>, which is <math>i</math> in binary. Since <math>x_{10010101_2} = 2 \cdot 5 \cdot 11 \cdot 19 = 2090</math>, <math>t = 10010101_2</math> = <math>\boxed{149}</math>. | ||
+ | |||
+ | ==Solution 2 (Painful Bash)== | ||
+ | We go through the terms and look for a pattern. We find that | ||
+ | |||
+ | <math>x_0 = 1</math> <math>x_8 = 7</math> | ||
+ | |||
+ | <math>x_1 = 2</math> <math>x_9 = 14</math> | ||
+ | |||
+ | <math>x_2 = 3</math> <math>x_{10} = 21</math> | ||
+ | |||
+ | <math>x_3 = 6</math> <math>x_{11} = 42</math> | ||
+ | |||
+ | <math>x_4 = 5</math> <math>x_{12} = 35</math> | ||
+ | |||
+ | <math>x_5 = 10</math> <math>x_{13} = 70</math> | ||
+ | |||
+ | <math>x_6 = 15</math> <math>x_{14} = 105</math> | ||
+ | |||
+ | <math>x_7 = 30</math> <math>x_{15} = 210</math> | ||
+ | |||
+ | Commit to the bash. Eventually, you will receive that <math>x_{149} = 2090</math>, so <math>\boxed{149}</math> is the answer. Trust me, this is worth the 10 index points. | ||
+ | |||
+ | <math>\textbf{-RootThreeOverTwo}</math> | ||
+ | |||
+ | ==Solution 3 (induction)== | ||
+ | |||
+ | Let <math>P_k</math> denote the <math>k</math>th prime. | ||
+ | Lemma: <math>x_{n+2^{k-1}} = P_k \cdot x_{n}</math> for all <math>0 \leq n \leq 2^{k-1} - 1.</math> | ||
+ | |||
+ | <math>\mathbf{\mathrm{Proof:}}</math> | ||
+ | |||
+ | We can prove this using induction. Assume that <math>x_{2^{k-1}-1} = \prod_{j=1}^{k-1} P_j. </math> Then, using the given recursion <math>x_{k+1} = \frac{x_np(x_n)}{X(x_n)}</math>, we would “start fresh” for <math>x_{2^{k-1}} = P_k.</math> It is then easy to see that then <math>\frac{x_n}{P_k}</math> just cycles through the previous <math>x_{2^{k-1}}</math> terms of <math>\{ x_n \}, </math> since the recursion process is the same and <math>P_k</math> being a factor of <math>x_n</math> is not affected until <math>n = 2 \cdot {2^{k-1}} = 2^k, </math> when given our assumption <math>x_{2^k - 1} = \prod_{j=1}^{k} P_j</math> and <math>n = 2^k</math> is now the least <math>n</math> such that <cmath>P_{k+1} = p(x_{2^{n-1}}), </cmath> in which <math>P_a = p(x_n)</math> where <math>a > k</math> is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, <math>x_{2^k} = P_{k+1}, </math> and the values of <math>x_n</math> just starts cycling through the previous <math>x_{2^k}</math> terms again until <math>x_{2^{k+1}}</math> when a new prime shows up in the prime factorization of <math>x_n, </math> when it starts cycling again, and so on. Using our base cases of <math>x_0</math> and <math>x_1, </math> our induction is complete. | ||
+ | Now, it is easy to see that <math>2090 = 2 \cdot 5 \cdot 11 \cdot 19 = P_1 \cdot P_3 \cdot P_5 \cdot P_8,</math> and by Lemma #1, the least positive integer <math>n</math> such that <math>19 | x_n</math> is <math>2^7. </math> By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just <math>2^7 + 2^4 + 2^2 + 2^0, </math> or <math>10010101_2 = \boxed{149}.</math> | ||
+ | |||
+ | -fidgetboss_4000 | ||
+ | |||
+ | |||
+ | == Video Solution == | ||
+ | https://youtu.be/SXZ01azDCGE?si=_lIcna68SgCcG3av | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
== See also == | == See also == | ||
{{AIME box|year=2014|n=II|num-b=14|after=Last Problem}} | {{AIME box|year=2014|n=II|num-b=14|after=Last Problem}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 16:44, 11 October 2023
Contents
[hide]Problem
For any integer , let be the smallest prime which does not divide Define the integer function to be the product of all primes less than if , and if Let be the sequence defined by , and for Find the smallest positive integer such that
Solution
Note that for any , for any prime , . This provides motivation to translate into a binary sequence .
Let the prime factorization of be written as , where is the th prime number. Then, for every in the prime factorization of , place a in the th digit of . This will result in the conversion .
Multiplication for the sequence will translate to addition for the sequence . Thus, we see that translates into . Since , and , corresponds to , which is in binary. Since , = .
Solution 2 (Painful Bash)
We go through the terms and look for a pattern. We find that
Commit to the bash. Eventually, you will receive that , so is the answer. Trust me, this is worth the 10 index points.
Solution 3 (induction)
Let denote the th prime. Lemma: for all
We can prove this using induction. Assume that Then, using the given recursion , we would “start fresh” for It is then easy to see that then just cycles through the previous terms of since the recursion process is the same and being a factor of is not affected until when given our assumption and is now the least such that in which where is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, and the values of just starts cycling through the previous terms again until when a new prime shows up in the prime factorization of when it starts cycling again, and so on. Using our base cases of and our induction is complete. Now, it is easy to see that and by Lemma #1, the least positive integer such that is By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just or
-fidgetboss_4000
Video Solution
https://youtu.be/SXZ01azDCGE?si=_lIcna68SgCcG3av
~MathProblemSolvingSkills.com
See also
2014 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 14 |
Followed by Last Problem | |
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.