Difference between revisions of "2023 AIME II Problems/Problem 15"
Jchaoisaac (talk | contribs) (add navigation links) |
Bxiao31415 (talk | contribs) (→Solution) |
||
Line 52: | Line 52: | ||
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | == 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>. | ||
+ | |||
+ | This encourages us to let <math>b_n = (a_n - 1)/2^n</math>. Rewriting the above equations, we have | ||
+ | <cmath> b_n = \begin{cases} b_{n-1}/2 & \text{if } 2 | (b_{n-1}+23)/2 \\ 1 &\text{if } 2\not\vert b_{n-1} \end{cases} </cmath> | ||
+ | Now, we start listing. We know that <math>b_1 = 11</math>, so <math>b_2 = 17</math>, <math>b_3 = 20</math>, <math>b_4 = 10</math>, <math>b_5 = 5</math>, <math>b_6 = 14</math>, <math>b_7 = 7</math>, <math>b_8 = 15</math>, <math>b_9 = 19</math>, <math>b_10 = 21</math>, <math>b_11 = 22</math>, <math>b_12 = 1</math>. Hence the sequence is periodic with period 11. | ||
+ | Note that <math>a_n = a_{n+1}</math> if and only if <math>b_n = b_{n+1}/2</math>, i.e. <math>b_n</math> is even. This occurrs when <math>n</math> is congruent to 0, 3, 4 or 6 mod 11. | ||
+ | |||
+ | From 1 to <math>1001 = 91 \times 11</math>, there are <math>91 \times 4 = 364</math> values of <math>n</math>. Since <math>1001</math> satisfies the criteria, we subtract 1 to get <math>\fbox{363}</math>, and we're done! | ||
+ | ~[[User:Bxiao31415|Bxiao31415]] | ||
== 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}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 18:38, 16 February 2023
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 , then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\end{enumerate}
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!
~Bxiao31415
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.