Difference between revisions of "2023 AIME II Problems/Problem 15"
Aidensharp (talk | contribs) |
Aidensharp (talk | contribs) m |
||
Line 31: | Line 31: | ||
We have the following results: | We have the following results: | ||
− | + | \begin{itemize} | |
− | \item If < | + | \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 < | + | \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 < | + | \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 < | + | \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 < | + | \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 < | + | \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 < | + | \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 < | + | \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 < | + | \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 < | + | \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 < | + | \item If <math>{\rm Rem} \left( n , 11 \right) = 10</math>, then <math>k_n = 21</math> and <math>b_n = 935</math>. |
− | \end{ | + | \end{itemize} |
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{itemize} \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{itemize}
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.