Difference between revisions of "2023 AIME II Problems/Problem 15"
R00tsofunity (talk | contribs) |
Aidensharp (talk | contribs) |
||
Line 31: | Line 31: | ||
We have the following results: | We have the following results: | ||
− | \begin{enumerate} | + | <math>\begin{enumerate} |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 0< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 0<math>, then </math>k_n = 22<math> and </math>b_n = 1<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 1< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 1<math>, then </math>k_n = 11<math> and </math>b_n = 1<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 2< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 2<math>, then </math>k_n = 17<math> and </math>b_n = 3<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 3< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 3<math>, then </math>k_n = 20<math> and </math>b_n = 7<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 4< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 4<math>, then </math>k_n = 10<math> and </math>b_n = 7<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 5< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 5<math>, then </math>k_n = 5<math> and </math>b_n = 7<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 6< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 6<math>, then </math>k_n = 14<math> and </math>b_n = 39<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 7< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 7<math>, then </math>k_n = 7<math> and </math>b_n = 39<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 8< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 8<math>, then </math>k_n = 15<math> and </math>b_n = 167<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 9< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 9<math>, then </math>k_n = 19<math> and </math>b_n = 423<math>. |
− | \item If <math>{\rm Rem} \left( n , 11 \right) = 10< | + | \item If </math>{\rm Rem} \left( n , 11 \right) = 10<math>, then </math>k_n = 21<math> and </math>b_n = 935<math>. |
− | \end{enumerate} | + | \end{enumerate}</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>. | 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>. |
Revision as of 10:49, 18 May 2023
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
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
.
We must have
. That is,
.
We find
.
Therefore, for each , we need to find smallest
, such that
We have the following results:
$\begin{enumerate}
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 0k_n = 22
b_n = 1$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 1
k_n = 11
b_n = 1$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 2
k_n = 17
b_n = 3$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 3
k_n = 20
b_n = 7$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 4
k_n = 10
b_n = 7$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 5
k_n = 5
b_n = 7$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 6
k_n = 14
b_n = 39$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 7
k_n = 7
b_n = 39$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 8
k_n = 15
b_n = 167$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 9
k_n = 19
b_n = 423$.
\item If$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \left( n , 11 \right) = 10
k_n = 21
b_n = 935$.
\end{enumerate}$ (Error compiling LaTeX. Unknown error_msg)
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
Now, we start listing. We know that
, so
,
,
,
,
,
,
,
,
,
,
. Hence the sequence is periodic with period 11.
Note that
if and only if
, i.e.
is even. This occurrs when
is congruent to 0, 3, 4 or 6 mod 11.
From 1 to , there are
values of
. Since
satisfies the criteria, we subtract 1 to get
, and we're done!
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
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.