Difference between revisions of "2023 AIME II Problems/Problem 15"
m (→Solution 3 (Similar to solution 2 but more explanation)) |
m (→Solution 3 (Similar to solution 2 but more explanation)) |
||
Line 92: | Line 92: | ||
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 | 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 | ||
− | < | + | <cmath> 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}</cmath>. |
− | Furthermore if quotient < | + | 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> | <cmath> 23b_n = 2^n q_n +1 = 2^{n+1} \frac{q_n}{2} +1 </cmath> | ||
− | Therefore < | + | 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> | <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 < | + | 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 = | <cmath> q_n = | ||
− | Finally, let us list out < | + | 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> | <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 < | + | 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) == | == Solution 4 (Binary Interpretation, Computer Scientists' Playground) == | ||
− | We first check that < | + | 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 < | + | 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 120: | Line 120: | ||
</cmath> | </cmath> | ||
− | Now note < | + | 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 < | + | 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, < | + | 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 < | + | 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> 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 < | + | 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 < | + | 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 < | + | 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 | ~ cocoa @ https://www.corgillogical.com |
Revision as of 16:03, 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
.
Furthermore if quotient
is even then
Therefore
if and only if
is even. And, if this is true, then
. Next, if
is odd, we must have
. Solving for
, we have
Therefore, if
is odd,
. In sum, our recursion is
Finally, let us list out
to find a pattern. Because
,
. Through our recursion, we continue like so:
Therefore
repeats with cycle length
. Since
if and only iff
is even, in each cycle, we have 4 satisfactory values of
. There are
complete cycles. There are 3 extra values in the last incomplete cycle. Therefore we obtain
.
Solution 4 (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.