Difference between revisions of "2023 AIME II Problems/Problem 15"
Bxiao31415 (talk | contribs) (→Solution) |
(→Solution 2) |
||
(15 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
For each positive integer <math>n</math> let <math>a_n</math> be the least positive integer multiple of <math>23</math> such that <math>a_n \equiv 1 \pmod{2^n}.</math> Find the number of positive integers <math>n</math> less than or equal to <math>1000</math> that satisfy <math>a_n = a_{n+1}.</math> | For each positive integer <math>n</math> let <math>a_n</math> be the least positive integer multiple of <math>23</math> such that <math>a_n \equiv 1 \pmod{2^n}.</math> Find the number of positive integers <math>n</math> less than or equal to <math>1000</math> that satisfy <math>a_n = a_{n+1}.</math> | ||
− | ==Solution== | + | ==Solution 1== |
Denote <math>a_n = 23 b_n</math>. | Denote <math>a_n = 23 b_n</math>. | ||
Line 19: | Line 20: | ||
Now, we find the smallest <math>m</math>, such that <math>2^m \equiv 1 \pmod{23}</math>. | Now, we find the smallest <math>m</math>, such that <math>2^m \equiv 1 \pmod{23}</math>. | ||
− | + | By Fermat's Theorem, we must have <math>m | \phi \left( 23 \right)</math>. That is, <math>m | 22</math>. | |
We find <math>m = 11</math>. | We find <math>m = 11</math>. | ||
Line 30: | Line 31: | ||
We have the following results: | We have the following results: | ||
− | + | ||
− | \ | + | If \({\rm Rem} \left( n , 11 \right) = 0\), then \(k_n = 22\) and \(b_n = 1\). |
− | \ | + | |
− | \ | + | If \({\rm Rem} \left( n , 11 \right) = 1\), then \(k_n = 11\) and \(b_n = 1\). |
− | \ | + | |
− | \ | + | If \({\rm Rem} \left( n , 11 \right) = 2\), then \(k_n = 17\) and \(b_n = 3\). |
− | \ | + | |
− | \ | + | If \({\rm Rem} \left( n , 11 \right) = 3\), then \(k_n = 20\) and \(b_n = 7\). |
− | \ | + | |
− | \ | + | If \({\rm Rem} \left( n , 11 \right) = 4\), then \(k_n = 10\) and \(b_n = 7\). |
− | \ | + | |
− | \ | + | If \({\rm Rem} \left( n , 11 \right) = 5\), then \(k_n = 5\) and \(b_n = 7\). |
− | + | ||
+ | If \({\rm Rem} \left( n , 11 \right) = 6\), then \(k_n = 14\) and \(b_n = 39\). | ||
+ | |||
+ | If \({\rm Rem} \left( n , 11 \right) = 7\), then \(k_n = 7\) and \(b_n = 39\). | ||
+ | |||
+ | If \({\rm Rem} \left( n , 11 \right) = 8\), then \(k_n = 15\) and \(b_n = 167\). | ||
+ | |||
+ | If \({\rm Rem} \left( n , 11 \right) = 9\), then \(k_n = 19\) and \(b_n = 423\). | ||
+ | |||
+ | If \({\rm Rem} \left( n , 11 \right) = 10\), then \(k_n = 21\) and \(b_n = 935\). | ||
Therefore, in each cycle, <math>n \in \left\{ 11 l , 11l + 1 , \cdots , 11l + 10 \right\}</math>, we have <math>n = 11l</math>, <math>11l + 3</math>, <math>11l + 4</math>, <math>11l + 6</math>, such that <math>b_n = b_{n+1}</math>. That is, <math>a_n = a_{n+1}</math>. | Therefore, in each cycle, <math>n \in \left\{ 11 l , 11l + 1 , \cdots , 11l + 10 \right\}</math>, we have <math>n = 11l</math>, <math>11l + 3</math>, <math>11l + 4</math>, <math>11l + 6</math>, such that <math>b_n = b_{n+1}</math>. That is, <math>a_n = a_{n+1}</math>. | ||
Line 53: | Line 63: | ||
== Solution 2 == | == Solution 2 == | ||
− | Observe that if <math>a_{n-1}</math> is divisible by <math>2^n</math>, <math>a_n = a_{n-1}</math>. If not, <math>a_n = a_{n-1} + 23 \cdot 2^{n-1}</math>. | + | Observe that if <math>a_{n-1} - 1</math> is divisible by <math>2^n</math>, <math>a_n = a_{n-1}</math>. If not, <math>a_n = a_{n-1} + 23 \cdot 2^{n-1}</math>. |
− | This encourages us to let <math>b_n = | + | This encourages us to let <math>b_n = \frac{a_n - 1}{2^n}</math>. Rewriting the above equations, we have |
− | <cmath> b_n = \begin{cases} b_{n-1} | + | <cmath> b_n = \begin{cases} \frac{b_{n-1}}{2} & \text{if } 2 \text{ } \vert \text{ } b_{n-1} \ \frac{b_{n-1}+23}{2} &\text{if } 2 \not\vert \text{ } b_{n-1} \end{cases} </cmath> |
− | + | The first few values of <math>b_n</math> are <math>11, 17, 20, 10, 5, 14, 7, 15, 19, 21,</math> and <math>22</math>. We notice that <math>b_{12} = b_1 = 11</math>, and thus the sequence is periodic with period <math>11</math>. | |
− | |||
− | From 1 to <math>1001 | + | Note that <math>a_n = a_{n+1}</math> if and only if <math>b_n</math> is even. This occurs when <math>n</math> is congruent to <math>0, 3, 4</math> or <math>6</math> mod <math>11</math>, giving four solutions for each period. |
+ | |||
+ | From <math>1</math> to <math>1001</math> (which is <math>91 \times 11</math>), there are <math>91 \times 4 = 364</math> values of <math>n</math>. We subtract <math>1</math> from the total since <math>1001</math> satisfies the criteria but is greater than <math>1000</math> to get a final answer of <math>\fbox{363}</math> . | ||
~[[User:Bxiao31415|Bxiao31415]] | ~[[User:Bxiao31415|Bxiao31415]] | ||
+ | |||
+ | (small changes by bobjoebilly and [[User:Iraevid13|IraeVid13]]) | ||
+ | |||
+ | == Solution 3 (Binary Interpretation, Computer Scientists' Playground) == | ||
+ | |||
+ | We first check that <math>\gcd(23, 2^n) = 1</math> hence we are always seeking a unique modular inverse of <math>23</math>, <math>b_n</math>, such that <math>a_n \equiv 23b_n \equiv 1 \mod{2^n}</math>. | ||
+ | |||
+ | |||
+ | Now that we know that <math>b_n</math> is unique, we proceed to recast this problem in binary. This is convenient because <math>x \mod{2^n}</math> is simply the last <math>n</math>-bits of <math>x</math> in binary, and if <math>x \equiv 1 \mod{2^n}</math>, it means that of the last <math>n</math> bits of <math>x</math>, only the rightmost bit (henceforth <math>0</math>th bit) is <math>1</math>. | ||
+ | |||
+ | Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example: | ||
+ | |||
+ | <cmath> | ||
+ | \begin{align} | ||
+ | 10111_2 \times 1011_2 &= 10111_2 \times (1000_2 + 10_2 + 1_2) \ | ||
+ | &= 10111000_2 + 101110_2 + 10111_2 \ | ||
+ | &= 11111101_2 | ||
+ | \end{align} | ||
+ | </cmath> | ||
+ | |||
+ | Now note <math>23 = 10111_2</math>, and recall that our objective is to progressively zero out the <math>n</math> leftmost bits of <math>a_n = 10111_2 \times b_n</math> except for the <math>0</math>th bit. | ||
+ | |||
+ | Write <math>b_n = \underline{c_{n-1}\cdots c_2c_1c_0}_2</math>, we note that <math>c_0</math> uniquely defines the <math>0</math>th bit of <math>a_n</math>, and once we determine <math>c_0</math>, <math>c_1</math> uniquely determines the <math>1</math>st bit of <math>a_n</math>, so on and so forth. | ||
+ | |||
+ | For example, <math>c_0 = 1</math> satisfies <math>a_1 \equiv10111_2 \times 1_2 \equiv 1 \mod{10_2}</math> | ||
+ | Next, we note that the second bit of <math>a_1</math> is <math>1</math>, so we must also have <math>c_1 = 1</math> in order to zero it out, giving | ||
+ | |||
+ | <cmath>a_2 \equiv 10111_2 \times 11_2 \equiv 101110_2 + a_1 \equiv 1000101_2 \equiv 01_2 \mod{100_2}</cmath> | ||
+ | |||
+ | <math>a_{n+1} = a_{n}</math> happens precisely when <math>c_n = 0</math>. In fact we can see this in action by working out <math>a_3</math>. Note that <math>a_2</math> has 1 on the <math>2</math>nd bit, so we must choose <math>c_2 = 1</math>. This gives | ||
+ | |||
+ | <cmath>a_3 \equiv 10111_2 \times 111_2 \equiv 1011100_2 + a_2 \equiv 10100001_2 \equiv 001_2 \mod{1000_2}</cmath> | ||
+ | |||
+ | Note that since the <math>3</math>rd and <math>4</math>th bit are <math>0</math>, <math>c_3 = c_4 = 0</math>, and this gives <math>a_3 = a_4 = a_5</math>. | ||
+ | |||
+ | |||
+ | It may seem that this process will take forever, but note that <math>23 = 10111_2</math> has <math>4</math> bits behind the leading digit, and in the worst case, the leading digits of <math>a_n</math> will have a cycle length of at most <math>16</math>. In fact, we find that the cycle length is <math>11</math>, and in the process found that <math>a_3 = a_4 = a_5</math>, <math>a_6 = a_7</math>, and <math>a_{11} = a_{12}</math>. | ||
+ | |||
+ | Since we have <math>90</math> complete cycles of length <math>11</math>, and the last partial cycle yields <math>a_{993} = a_{994} = a_{995}</math> and <math>a_{996} = a_{997}</math>, we have a total of <math>90 \times 4 + 3 = \boxed{363}</math> values of <math>n \le 1000</math> such that <math>a_n = a_{n+1}</math> | ||
+ | |||
+ | ~ cocoa @ https://www.corgillogical.com | ||
+ | |||
+ | |||
+ | == Video Solution == | ||
+ | https://youtu.be/ujP-V170vvI | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
+ | |||
== See also == | == See also == | ||
{{AIME box|year=2023|num-b=14|after=Last Problem|n=II}} | {{AIME box|year=2023|num-b=14|after=Last Problem|n=II}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 07:13, 1 February 2024
Contents
[hide]Problem
For each positive integer let be the least positive integer multiple of such that Find the number of positive integers less than or equal to that satisfy
Solution 1
Denote . Thus, for each , we need to find smallest positive integer , such that
Thus, we need to find smallest , such that
Now, we find the smallest , such that . By Fermat's Theorem, we must have . That is, . We find .
Therefore, for each , we need to find smallest , such that
We have the following results:
If
If
If
If
If
If
If
If
If
If
If
Therefore, in each cycle, , we have , , , , such that . That is, . At the boundary of two consecutive cycles, .
We have . Therefore, the number of feasible is .
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Solution 2
Observe that if is divisible by , . If not, .
This encourages us to let . Rewriting the above equations, we have The first few values of are and . We notice that , and thus the sequence is periodic with period .
Note that if and only if is even. This occurs when is congruent to or mod , giving four solutions for each period.
From to (which is ), there are values of . We subtract from the total since satisfies the criteria but is greater than to get a final answer of . ~Bxiao31415
(small changes by bobjoebilly and IraeVid13)
Solution 3 (Binary Interpretation, Computer Scientists' Playground)
We first check that hence we are always seeking a unique modular inverse of , , such that .
Now that we know that is unique, we proceed to recast this problem in binary. This is convenient because is simply the last -bits of in binary, and if , it means that of the last bits of , only the rightmost bit (henceforth th bit) is .
Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example:
Now note , and recall that our objective is to progressively zero out the leftmost bits of except for the th bit.
Write , we note that uniquely defines the th bit of , and once we determine , uniquely determines the st bit of , so on and so forth.
For example, satisfies Next, we note that the second bit of is , so we must also have in order to zero it out, giving
happens precisely when . In fact we can see this in action by working out . Note that has 1 on the nd bit, so we must choose . This gives
Note that since the rd and th bit are , , and this gives .
It may seem that this process will take forever, but note that has bits behind the leading digit, and in the worst case, the leading digits of will have a cycle length of at most . In fact, we find that the cycle length is , and in the process found that , , and .
Since we have complete cycles of length , and the last partial cycle yields and , we have a total of values of such that
~ cocoa @ https://www.corgillogical.com
Video Solution
~MathProblemSolvingSkills.com
See also
2023 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.