Difference between revisions of "2023 AIME II Problems/Problem 15"
m (→Solution 1) |
(→Solution 2) |
||
(One intermediate revision by the same user not shown) | |||
Line 71: | Line 71: | ||
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. | 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>. | + | 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]] | ||
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.