Difference between revisions of "2023 AIME II Problems/Problem 15"
Bxiao31415 (talk | contribs) (→Solution 2) |
(→Solution 2) |
||
(13 intermediate revisions by 9 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>. | |
− | |||
− | + | 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}} |
Latest revision as of 08:13, 1 February 2024
Contents
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 \({\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, , 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.