2023 AIME II Problems/Problem 15

Revision as of 16:57, 16 February 2023 by Stevenyiweichen (talk | contribs) (Created page with "==Solution== Denote <math>a_n = 23 b_n</math>. Thus, for each <math>n</math>, we need to find smallest positive integer <math>k_n</math>, such that \[ 23 b_n = 2^n k_n + 1 ....")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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)