2022 AMC 10B Problems/Problem 25
- The following problem is from both the 2022 AMC 10B #25 and 2022 AMC 12B #23, so both problems redirect to this page.
Contents
- 1 Problem
- 2 Solution 1
- 3 Solution 2
- 4 Solution 3
- 5 Solution 4
- 6 Solution 5
- 7 Video Solution by MOP 2024
- 8 Video Solution by ThePuzzlr
- 9 Video Solution by Steven Chen
- 10 Video Solution by OmegaLearn Using Binary and Modular Arithmetic
- 11 Video Solution by The Power of Logic
- 12 Video Solution by Interstigation
- 13 See Also
Problem
Let be a sequence of numbers, where each is either or . For each positive integer , define Suppose for all . What is the value of the sum
Solution 1
In binary numbers, we have It follows that We obtain by subtracting the equations: We work from right to left: For all we conclude that
- if and only if
- if and only if
Finally, we get from which ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
~MRENTHUSIASM
Solution 2
First, notice that Then since is the modular inverse of in , we can perform the Euclidean Algorithm to find it for .
Starting with , Now, take both sides : Using Fermat's Little Theorem, Thus, Therefore,
We may repeat this same calculation with to yield Now, we notice that is basically an integer expressed in binary form with bits. This gives rise to a simple inequality, Since the maximum possible number that can be generated with bits is Looking at our calculations for and , we see that the only valid integers that satisfy that constraint are . ~zoomanTV
Solution 3
As in Solution 2, we note that We also know that and , this implies: Dividing by , we can isolate the previous sums: The maximum value of occurs when every is equal to . Even when this happens, the value of is less than . Therefore, we can construct the following inequalities: From these two equations, we can deduce that both and are less than .
Reducing and we see that and
The powers of repeat every
Therefore, and Substituing this back into the above equations, and
Since and are integers less than , the only values of and are and respectively.
The requested sum is -Benedict T (countmath1)
Solution 4
Note that, as in Solution 2, we have This is because and Note that Therefore, Multiplying both sides by 7 gives us We can write and for some a and b. Substituting, we get Therefore, our answer can be written as Another thing to notice is that a and b are integers between 0 and 6. This is because which is which only holds when a is less than 7 because the right is very small positive number, so the left must be positive, too. Clearly, a is also non-negative, because otherwise, which would mean which cannot happen, so a is greater than 0. A similar explanation for b shows that b is an integer between 0 and 6 inclusive.
Going back to the solution, if our answer to the problem is n, then and so we can try the five option choices and see which one, when multiplied by 7 and added to some whole number between 0 and 6 results in a multiple of 16. Trying all the option choices, we see that you need to add 7n to something more than 6 to equal a multiple of 16 other than for option A. Therefore, the answer is
-Rutvik Arora (youtube channel: https://www.youtube.com/channel/UCkgAgmNAQV8WGTOazGYEGwg) -whatdohumanitarianseat made a small edit for a typo
Solution 5
Given that , we have where is integer.
Notice that Thus, Obviously, , , , so . For each , must be 0 or 1, and is an integer, so we can repeat the recursion to yield So for any non-negative integer , we can find that , , ,
Video Solution by MOP 2024
~r00tsOfUnity
Video Solution by ThePuzzlr
~ ThePuzzlr
Video Solution by Steven Chen
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution by OmegaLearn Using Binary and Modular Arithmetic
~ pi_is_3.14
Video Solution by The Power of Logic
Video Solution by Interstigation
~Interstigation
See Also
2022 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last problem | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
2022 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 22 |
Followed by Problem 24 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.