Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 AIME II Problems/Problem 15"

(→‎Solution)
(→‎Solution 2)
Line 57: Line 57:
 
This encourages us to let <math>b_n = (a_n - 1)/2^n</math>. Rewriting the above equations, we have
 
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>
 
<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.
+
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.
 
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.
  

Revision as of 17:39, 16 February 2023

For each positive integer $n$ let $a_n$ be the least positive integer multiple of $23$ such that $a_n \equiv 1 \pmod{2^n}.$ Find the number of positive integers $n$ less than or equal to $1000$ that satisfy $a_n = a_{n+1}.$

Solution

Denote $a_n = 23 b_n$. Thus, for each $n$, we need to find smallest positive integer $k_n$, such that \[ 23 b_n = 2^n k_n + 1 . \]

Thus, we need to find smallest $k_n$, such that \[ 2^n k_n \equiv - 1 \pmod{23} . \]

Now, we find the smallest $m$, such that $2^m \equiv 1 \pmod{23}$. We must have $m | \phi \left( 23 \right)$. That is, $m | 22$. We find $m = 11$.

Therefore, for each $n$, we need to find smallest $k_n$, such that \[ 2^{{\rm Rem} \left( n , 11 \right)} k_n \equiv - 1 \pmod{23} . \]

We have the following results: \begin{enumerate} \item If ${\rm Rem} \left( n , 11 \right) = 0$, then $k_n = 22$ and $b_n = 1$. \item If ${\rm Rem} \left( n , 11 \right) = 1$, then $k_n = 11$ and $b_n = 1$. \item If ${\rm Rem} \left( n , 11 \right) = 2$, then $k_n = 17$ and $b_n = 3$. \item If ${\rm Rem} \left( n , 11 \right) = 3$, then $k_n = 20$ and $b_n = 7$. \item If ${\rm Rem} \left( n , 11 \right) = 4$, then $k_n = 10$ and $b_n = 7$. \item If ${\rm Rem} \left( n , 11 \right) = 5$, then $k_n = 5$ and $b_n = 7$. \item If ${\rm Rem} \left( n , 11 \right) = 6$, then $k_n = 14$ and $b_n = 39$. \item If ${\rm Rem} \left( n , 11 \right) = 7$, then $k_n = 7$ and $b_n = 39$. \item If ${\rm Rem} \left( n , 11 \right) = 8$, then $k_n = 15$ and $b_n = 167$. \item If ${\rm Rem} \left( n , 11 \right) = 9$, then $k_n = 19$ and $b_n = 423$. \item If ${\rm Rem} \left( n , 11 \right) = 10$, then $k_n = 21$ and $b_n = 935$. \end{enumerate}

Therefore, in each cycle, $n \in \left\{ 11 l , 11l + 1 , \cdots , 11l + 10 \right\}$, we have $n = 11l$, $11l + 3$, $11l + 4$, $11l + 6$, such that $b_n = b_{n+1}$. That is, $a_n = a_{n+1}$. At the boundary of two consecutive cycles, $b_{11L + 10} \neq b_{11 \left(l + 1 \right)}$.

We have $1000 = 90 \cdot 11 + 10$. Therefore, the number of feasible $n$ is $91 \cdot 4 - 1 = \boxed{\textbf{(363) }}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 2

Observe that if $a_{n-1}$ is divisible by $2^n$, $a_n = a_{n-1}$. If not, $a_n = a_{n-1} + 23 \cdot 2^{n-1}$.

This encourages us to let $b_n = (a_n - 1)/2^n$. Rewriting the above equations, we have \[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}\] Now, we start listing. We know that $b_1 = 11$, so $b_2 = 17$, $b_3 = 20$, $b_4 = 10$, $b_5 = 5$, $b_6 = 14$, $b_7 = 7$, $b_8 = 15$, $b_9 = 19$, $b_{10} = 21$, $b_{11} = 22$, $b_{12} = 1$. Hence the sequence is periodic with period 11. Note that $a_n = a_{n+1}$ if and only if $b_n = b_{n+1}/2$, i.e. $b_n$ is even. This occurrs when $n$ is congruent to 0, 3, 4 or 6 mod 11.

From 1 to $1001 = 91 \times 11$, there are $91 \times 4 = 364$ values of $n$. Since $1001$ satisfies the criteria, we subtract 1 to get $\fbox{363}$, 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AIME_II_Problems/Problem_15&oldid=189737"