Difference between revisions of "2023 AIME II Problems/Problem 15"
(→Solution 2) |
|||
Line 76: | Line 76: | ||
(small changes by bobjoebilly and [[User:Iraevid13|IraeVid13]]) | (small changes by bobjoebilly and [[User:Iraevid13|IraeVid13]]) | ||
− | == Solution 3 ( | + | == Solution 3 (Similar to solution 2 but more explanation) == |
+ | Let <math>a_n = 23b_n</math>. Note that if | ||
+ | <cmath> 23 b_{n+1} \equiv 1 \pmod{2^{n+1}} </cmath> | ||
+ | Then | ||
+ | <cmath> 23 b_{n+1} \equiv 1 \pmod{2^{n}} </cmath> | ||
+ | Also | ||
+ | <cmath> 23 b_n \equiv 1 \pmod{2^n} </cmath> | ||
+ | Therefore | ||
+ | <cmath> b_n \equiv b_{n+1} \equiv 23^{-1} \pmod{2^n} </cmath> | ||
+ | Then | ||
+ | <cmath> b_{n+1} \equiv b_n, b_n + 2^n \pmod{2^{n+1}} </cmath> | ||
+ | So | ||
+ | <cmath> b_{n+1} = b_n, b_n + 2^n </cmath> | ||
+ | Since <math>1 \le b_n \le 2^n</math> and <math>1 \le b_{n+1} \le 2^{n+1}</math> as <math>a_n</math> is the _least_ positive integer multiple of 23. | ||
− | + | Now suppose <math>b_{n+1} = b_n</math>. Define <math>q_n</math> to be the quotient of <math>23b_n</math> divided by <math>2^n</math>. Then | |
+ | <math></math> 23b_n = 2^n q_n + 1 \text{ and } 23b_{n+1} = 23b_n = 2^{n+1} q_{n+1} + 1 = 2^n q_n + 1 \implies q_{n+1} = \frac{q_n}{2}<math>. | ||
+ | Furthermore if quotient </math>q_n<math> is even then | ||
+ | <cmath> 23b_n = 2^n q_n +1 = 2^{n+1} \frac{q_n}{2} +1 </cmath> | ||
+ | Therefore </math>b_{n+1} = b_n<math> if and only if </math>q_n<math> is even. And, if this is true, then </math>q_{n+1} = \frac{q_n}{2}<math>. Next, if </math>q_n<math> is odd, we must have </math>b_{n+1} = b_n + 2^n<math>. Solving for </math>q_{n+1}<math>, we have | ||
+ | <cmath> 23b_{n+1} = 2^{n+1} q_{n+1} + 1 \implies 23b_n + 23 \cdot 2^n = 2^{n+1} q_{n+1} + 1 \implies 2^n q_n + 1 + 23 = 2^{n+1} q_{n+1} + 1 \implies q_{n+1} = \frac{q_n + 1}{2} + 11 </cmath> | ||
+ | Therefore, if </math>q_n<math> is odd, </math>q_{n+1} = \frac{q_n + 1}{2} + 11<math>. In sum, our recursion is | ||
+ | <cmath> q_n = \begin{cases} \frac{q_{n-1}}{2} & \text{if } 2 \text{ } \vert \text{ } q_{n-1} \\ \frac{q_{n-1}+1}{2} + 11 &\text{if } 2 \not\vert \text{ } q_{n-1} \end{cases} </cmath> | ||
+ | Finally, let us list out </math>q_n<math> to find a pattern. Because </math>a_1 = 23<math>, </math>q_1 = 11<math>. Through our recursion, we continue like so: | ||
+ | <cmath> q_1 = 11, q_2 = 17, q_2 = 20, q_3 = 10, q_4 = 5, q_6 = 14, q_7 = 7, q_8 = 15, q_9 = 19, q_10 = 21, q_11 = 22, q_12 = 11, \dots </cmath> | ||
+ | Therefore </math>q_n<math> repeats with cycle length </math>11<math>. Since </math>a_{n+1} = a_n<math> if and only iff </math>q_n<math> is even, in each cycle, we have 4 satisfactory values of </math>n<math>. There are </math>\frac{1000 - 10}{11} = 90<math> complete cycles. There are 3 extra values in the last incomplete cycle. Therefore we obtain </math>90 \cdot 4 + 3 = \fbox{363}<math>. | ||
+ | == Solution 4 (Binary Interpretation, Computer Scientists' Playground) == | ||
− | Now that we know that <math>b_n< | + | 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: | Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example: | ||
Line 93: | Line 120: | ||
</cmath> | </cmath> | ||
− | Now note <math>23 = 10111_2< | + | 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< | + | 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< | + | 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< | + | 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> | <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>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> | <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< | + | 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< | + | 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< | + | 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}$ |
~ cocoa @ https://www.corgillogical.com | ~ cocoa @ https://www.corgillogical.com |
Revision as of 16:00, 29 December 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 (Similar to solution 2 but more explanation)
Let . Note that if
Then
Also
Therefore
Then
So
Since
and
as
is the _least_ positive integer multiple of 23.
Now suppose . Define
to be the quotient of
divided by
. Then
$$ (Error compiling LaTeX. Unknown error_msg) 23b_n = 2^n q_n + 1 \text{ and } 23b_{n+1} = 23b_n = 2^{n+1} q_{n+1} + 1 = 2^n q_n + 1 \implies q_{n+1} = \frac{q_n}{2}
q_n
b_{n+1} = b_n
q_n
q_{n+1} = \frac{q_n}{2}
q_n
b_{n+1} = b_n + 2^n
q_{n+1}
q_n
q_{n+1} = \frac{q_n + 1}{2} + 11
q_n
a_1 = 23
q_1 = 11
q_n
11
a_{n+1} = a_n
q_n
n
\frac{1000 - 10}{11} = 90
90 \cdot 4 + 3 = \fbox{363}$.
== Solution 4 (Binary Interpretation, Computer Scientists' Playground) ==
We first check that$ (Error compiling LaTeX. Unknown error_msg)\gcd(23, 2^n) = 123
b_n
a_n \equiv 23b_n \equiv 1 \mod{2^n}$.
Now that we know that$ (Error compiling LaTeX. Unknown error_msg)b_nx \mod{2^n}
n
x
x \equiv 1 \mod{2^n}
n
x
0
1$.
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$ (Error compiling LaTeX. Unknown error_msg)23 = 10111_2n
a_n = 10111_2 \times b_n
0$th bit.
Write$ (Error compiling LaTeX. Unknown error_msg)b_n = \underline{c_{n-1}\cdots c_2c_1c_0}_2c_0
0
a_n
c_0
c_1
1
a_n$, so on and so forth.
For example,$ (Error compiling LaTeX. Unknown error_msg)c_0 = 1a_1 \equiv10111_2 \times 1_2 \equiv 1 \mod{10_2}
a_1
1
c_1 = 1$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>$ (Error compiling LaTeX. Unknown error_msg)a_{n+1} = a_{n}c_n = 0
a_3
a_2
2
c_2 = 1$. 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$ (Error compiling LaTeX. Unknown error_msg)34
0
c_3 = c_4 = 0
a_3 = a_4 = a_5$.
It may seem that this process will take forever, but note that$ (Error compiling LaTeX. Unknown error_msg)23 = 10111_24
a_n
16
11
a_3 = a_4 = a_5
a_6 = a_7
a_{11} = a_{12}$.
Since we have$ (Error compiling LaTeX. Unknown error_msg)9011
a_{993} = a_{994} = a_{995}
a_{996} = a_{997}
90 \times 4 + 3 = \boxed{363}
n \le 1000
a_n = a_{n+1}$
~ 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.