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"

m (→‎Solution 2)
(→‎Solution 2)
 
(7 intermediate revisions by 5 users not shown)
Line 2: Line 2:
 
For each positive integer <math>n</math> let <math>a_n</math> be the least positive integer multiple of <math>23</math> such that <math>a_n \equiv 1 \pmod{2^n}.</math> Find the number of positive integers <math>n</math> less than or equal to <math>1000</math> that satisfy <math>a_n = a_{n+1}.</math>
 
For each positive integer <math>n</math> let <math>a_n</math> be the least positive integer multiple of <math>23</math> such that <math>a_n \equiv 1 \pmod{2^n}.</math> Find the number of positive integers <math>n</math> less than or equal to <math>1000</math> that satisfy <math>a_n = a_{n+1}.</math>
  
−
==Solution==
+
==Solution 1==
  
 
Denote <math>a_n = 23 b_n</math>.
 
Denote <math>a_n = 23 b_n</math>.
Line 20: Line 20:
  
 
Now, we find the smallest <math>m</math>, such that <math>2^m \equiv 1 \pmod{23}</math>.
 
Now, we find the smallest <math>m</math>, such that <math>2^m \equiv 1 \pmod{23}</math>.
−
We must have <math>m | \phi \left( 23 \right)</math>. That is, <math>m | 22</math>.
+
By Fermat's Theorem, we must have <math>m | \phi \left( 23 \right)</math>. That is, <math>m | 22</math>.
 
We find <math>m = 11</math>.
 
We find <math>m = 11</math>.
  
Line 31: Line 31:
  
 
We have the following results:
 
We have the following results:
−
\begin{itemize}
+
 
−
\item If <math>{\rm Rem} \left( n , 11 \right) = 0</math>, then <math>k_n = 22</math> and <math>b_n = 1</math>.
+
If \({\rm Rem} \left( n , 11 \right) = 0\), then \(k_n = 22\) and \(b_n = 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</math>, then <math>k_n = 17</math> and <math>b_n = 3</math>.
+
If \({\rm Rem} \left( n , 11 \right) = 1\), then \(k_n = 11\) and \(b_n = 1\).
−
\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</math>, then <math>k_n = 10</math> and <math>b_n = 7</math>.
+
If \({\rm Rem} \left( n , 11 \right) = 2\), then \(k_n = 17\) and \(b_n = 3\).
−
\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</math>, then <math>k_n = 14</math> and <math>b_n = 39</math>.
+
If \({\rm Rem} \left( n , 11 \right) = 3\), then \(k_n = 20\) and \(b_n = 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</math>, then <math>k_n = 15</math> and <math>b_n = 167</math>.
+
If \({\rm Rem} \left( n , 11 \right) = 4\), then \(k_n = 10\) and \(b_n = 7\).
−
\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</math>, then <math>k_n = 21</math> and <math>b_n = 935</math>.
+
If \({\rm Rem} \left( n , 11 \right) = 5\), then \(k_n = 5\) and \(b_n = 7\).
−
\end{itemize}
+
 
 +
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, <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>.
Line 62: 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> (<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 geta 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]]
  
−
(small changes by bobjoebilly)
+
(small changes by bobjoebilly and [[User:Iraevid13|IraeVid13]])
  
 
== Solution 3 (Binary Interpretation, Computer Scientists' Playground) ==
 
== Solution 3 (Binary Interpretation, Computer Scientists' Playground) ==
Line 106: Line 114:
  
 
~ cocoa @ https://www.corgillogical.com
 
~ cocoa @ https://www.corgillogical.com
 +
 +
 +
== Video Solution ==
 +
https://youtu.be/ujP-V170vvI
 +
 +
~MathProblemSolvingSkills.com
 +
 +
 +
  
 
== See also ==
 
== See also ==

Latest revision as of 07:13, 1 February 2024

Problem

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 1

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}$. By Fermat's Theorem, 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:

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, $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} - 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 = \frac{a_n - 1}{2^n}$. Rewriting the above equations, we have \[b_n = \begin{cases} \frac{b_{n-1}}{2} & \text{if } 2 \text{ } \vert \text{ } b_{n-1} \\ \frac{b_{n-1}+23}{2} &\text{if } 2 \not\vert \text{ } b_{n-1} \end{cases}\] The first few values of $b_n$ are $11, 17, 20, 10, 5, 14, 7, 15, 19, 21,$ and $22$. We notice that $b_{12} = b_1 = 11$, and thus the sequence is periodic with period $11$.

Note that $a_n = a_{n+1}$ if and only if $b_n$ is even. This occurs when $n$ is congruent to $0, 3, 4$ or $6$ mod $11$, giving four solutions for each period.

From $1$ to $1001$ (which is $91 \times 11$), there are $91 \times 4 = 364$ values of $n$. We subtract $1$ from the total since $1001$ satisfies the criteria but is greater than $1000$ to get a final answer of $\fbox{363}$ . ~Bxiao31415

(small changes by bobjoebilly and IraeVid13)

Solution 3 (Binary Interpretation, Computer Scientists' Playground)

We first check that $\gcd(23, 2^n) = 1$ hence we are always seeking a unique modular inverse of $23$, $b_n$, such that $a_n \equiv 23b_n \equiv 1 \mod{2^n}$.


Now that we know that $b_n$ is unique, we proceed to recast this problem in binary. This is convenient because $x \mod{2^n}$ is simply the last $n$-bits of $x$ in binary, and if $x \equiv 1 \mod{2^n}$, it means that of the last $n$ bits of $x$, only the rightmost bit (henceforth $0$th bit) is $1$.

Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example:

\begin{align} 10111_2 \times 1011_2 &= 10111_2 \times (1000_2 + 10_2 + 1_2) \\ &= 10111000_2 + 101110_2 + 10111_2 \\ &= 11111101_2 \end{align}

Now note $23 = 10111_2$, and recall that our objective is to progressively zero out the $n$ leftmost bits of $a_n = 10111_2 \times b_n$ except for the $0$th bit.

Write $b_n = \underline{c_{n-1}\cdots c_2c_1c_0}_2$, we note that $c_0$ uniquely defines the $0$th bit of $a_n$, and once we determine $c_0$, $c_1$ uniquely determines the $1$st bit of $a_n$, so on and so forth.

For example, $c_0 = 1$ satisfies $a_1 \equiv10111_2 \times 1_2 \equiv 1 \mod{10_2}$ Next, we note that the second bit of $a_1$ is $1$, so we must also have $c_1 = 1$ in order to zero it out, giving

\[a_2 \equiv 10111_2 \times 11_2 \equiv 101110_2 + a_1 \equiv 1000101_2 \equiv 01_2 \mod{100_2}\]

$a_{n+1} = a_{n}$ happens precisely when $c_n = 0$. In fact we can see this in action by working out $a_3$. Note that $a_2$ has 1 on the $2$nd bit, so we must choose $c_2 = 1$. This gives

\[a_3 \equiv 10111_2 \times 111_2 \equiv 1011100_2 + a_2 \equiv 10100001_2 \equiv 001_2 \mod{1000_2}\]

Note that since the $3$rd and $4$th bit are $0$, $c_3 = c_4 = 0$, and this gives $a_3 = a_4 = a_5$.


It may seem that this process will take forever, but note that $23 = 10111_2$ has $4$ bits behind the leading digit, and in the worst case, the leading digits of $a_n$ will have a cycle length of at most $16$. In fact, we find that the cycle length is $11$, and in the process found that $a_3 = a_4 = a_5$, $a_6 = a_7$, and $a_{11} = a_{12}$.

Since we have $90$ complete cycles of length $11$, and the last partial cycle yields $a_{993} = a_{994} = a_{995}$ and $a_{996} = a_{997}$, we have a total of $90 \times 4 + 3 = \boxed{363}$ values of $n \le 1000$ such that $a_n = a_{n+1}$

~ cocoa @ https://www.corgillogical.com


Video Solution

https://youtu.be/ujP-V170vvI

~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. AMC logo.png

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