Difference between revisions of "2021 AIME I Problems/Problem 7"
(→Solution 2) |
MRENTHUSIASM (talk | contribs) (→Solution 1) |
||
(77 intermediate revisions by 15 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Find the number of pairs <math>(m,n)</math> of positive integers with <math>1\le m<n\le 30</math> such that there exists a real number <math>x</math> satisfying<cmath>\sin(mx)+\sin(nx)=2.</cmath> | + | Find the number of pairs <math>(m,n)</math> of positive integers with <math>1\le m<n\le 30</math> such that there exists a real number <math>x</math> satisfying <cmath>\sin(mx)+\sin(nx)=2.</cmath> |
==Solution 1== | ==Solution 1== | ||
− | + | It is trivial that the maximum value of <math>\sin \theta</math> is <math>1</math>, is achieved at <math>\theta = \frac{\pi}{2}+2k\pi</math> for some integer <math>k</math>. | |
This implies that <math>\sin(mx) = \sin(nx) = 1</math>, and that <math>mx = \frac{\pi}{2}+2a\pi</math> and <math>nx = \frac{\pi}{2}+2b\pi</math>, for integers <math>a, b</math>. | This implies that <math>\sin(mx) = \sin(nx) = 1</math>, and that <math>mx = \frac{\pi}{2}+2a\pi</math> and <math>nx = \frac{\pi}{2}+2b\pi</math>, for integers <math>a, b</math>. | ||
Line 12: | Line 12: | ||
If <math>k = 1</math>, then <math>m \equiv n \equiv 1 \pmod 4</math>. This corresponds to choosing two elements from the set <math>\{1, 5, 9, 13, 17, 21, 25, 29\}</math>. There are <math>\binom 82</math> ways to do so. | If <math>k = 1</math>, then <math>m \equiv n \equiv 1 \pmod 4</math>. This corresponds to choosing two elements from the set <math>\{1, 5, 9, 13, 17, 21, 25, 29\}</math>. There are <math>\binom 82</math> ways to do so. | ||
− | If <math>k < 1</math>, by multiplying <math>m</math> and <math>n</math> by the same constant <math>c = \frac{1}{k}</math>, we have that <math>mc \equiv nc \equiv 1 \pmod 4</math>. Then either <math>m \equiv n \equiv 1 \pmod 4</math>, or <math>m \equiv n \equiv 3 \pmod 4</math>. But the first case was already counted, so we don't need to consider that case. The other case corresponds to choosing two numbers from the set <math>\{3, 7, 11, 15, 19, 23, 27\}</math>. There are <math>\binom 72</math> ways here. | + | If <math>k < 1</math>, by multiplying <math>m</math> and <math>n</math> by the same constant <math>c = \frac{1}{k}</math>, we have that <math>mc \equiv nc \equiv 1 \pmod 4</math>. Then either <math>m \equiv n \equiv 1 \pmod 4</math>, or <math>m \equiv n \equiv 3 \pmod 4</math>. But the first case was already counted, so we don't need to consider that case. The other case corresponds to choosing two numbers from the set <math>\{3, 7, 11, 15, 19, 23, 27\}</math>. There are <math>\binom 72</math> ways here. (This argument seems to have a logical flaw) |
Finally, if <math>k > 1</math>, note that <math>k</math> must be an integer. This means that <math>m, n</math> belong to the set <math>\{k, 5k, 9k, \dots\}</math>, or <math>\{3k, 7k, 11k, \dots\}</math>. Taking casework on <math>k</math>, we get the sets <math>\{2, 10, 18, 26\}, \{6, 14, 22, 30\}, \{4, 20\}, \{12, 28\}</math>. Some sets have been omitted; this is because they were counted in the other cases already. This sums to <math>\binom 42 + \binom 42 + \binom 22 + \binom 22</math>. | Finally, if <math>k > 1</math>, note that <math>k</math> must be an integer. This means that <math>m, n</math> belong to the set <math>\{k, 5k, 9k, \dots\}</math>, or <math>\{3k, 7k, 11k, \dots\}</math>. Taking casework on <math>k</math>, we get the sets <math>\{2, 10, 18, 26\}, \{6, 14, 22, 30\}, \{4, 20\}, \{12, 28\}</math>. Some sets have been omitted; this is because they were counted in the other cases already. This sums to <math>\binom 42 + \binom 42 + \binom 22 + \binom 22</math>. | ||
− | In total, there are <math>\binom 82 + \binom 72 + \binom 42 + \binom 42 + \binom 22 + \binom 22 = \boxed{ | + | In total, there are <math>\binom 82 + \binom 72 + \binom 42 + \binom 42 + \binom 22 + \binom 22 = \boxed{063}</math> pairs of <math>(m, n)</math>. |
This solution was brought to you by ~Leonard_my_dude~ | This solution was brought to you by ~Leonard_my_dude~ | ||
Line 28: | Line 28: | ||
This means that <math>mx = \frac{\pi}{2} + 2\pi\alpha</math> and <math>nx = \frac{\pi}{2} + 2\pi\beta</math> for any integers <math>\alpha</math> and <math>\beta</math>. | This means that <math>mx = \frac{\pi}{2} + 2\pi\alpha</math> and <math>nx = \frac{\pi}{2} + 2\pi\beta</math> for any integers <math>\alpha</math> and <math>\beta</math>. | ||
− | As in | + | As in Solution 1, take the ratio of the two equations: |
− | <cmath>\frac{ | + | <cmath>\frac{mx}{nx} = \frac{\frac{\pi}{2}+2\pi\alpha}{\frac{\pi}{2}+2\pi\beta} \implies \frac{m}{n} = \frac{\frac{1}{2}+2\alpha}{\frac{1}{2}+2\beta} \implies \frac{m}{n} = \frac{4\alpha+1}{4\beta+1}</cmath> |
− | + | Now notice that the numerator and denominator of <math>\frac{4\alpha+1}{4\beta+1}</math> are both odd, which means that <math>m</math> and <math>n</math> have the same power of two (the powers of 2 cancel out). | |
+ | |||
+ | Let the common power be <math>p</math>: then <math>m = 2^p\cdot a</math>, and <math>n = 2^p\cdot b</math> where <math>a</math> and <math>b</math> are integers between 1 and 30. | ||
+ | |||
+ | We can now rewrite the equation: | ||
+ | <cmath>\frac{2^p\cdot a}{2^p\cdot b} = \frac{4\alpha+1}{4\beta+1} \implies \frac{a}{b} = \frac{4\alpha+1}{4\beta+1}</cmath> | ||
+ | |||
+ | Now it is easy to tell that <math>a \equiv 1 (</math>mod <math>4)</math> and <math>b \equiv 1 (</math>mod <math>4)</math>. However, there is another case: that | ||
+ | |||
+ | <math>a \equiv 3 (</math>mod <math>4)</math> and <math>b \equiv 3 (</math>mod <math>4)</math>. This is because multiplying both <math>4\alpha+1</math> and <math>4\beta+1</math> by <math>-1</math> will not change the fraction, but each congruence will be changed to <math>-1 (</math>mod <math>4) \equiv 3 (</math>mod <math>4)</math>. | ||
+ | |||
+ | From the first set of congruences, we find that <math>a</math> and <math>b</math> can be two of | ||
+ | <math>\{1, 5, 9, \ldots, 29\}</math>. | ||
+ | |||
+ | From the second set of congruences, we find that <math>a</math> and <math>b</math> can be two of | ||
+ | <math>\{3, 7, 11, \ldots, 27\}</math>. | ||
+ | |||
+ | Now all we have to do is multiply by <math>2^p</math> to get back to <math>m</math> and <math>n</math>. | ||
+ | Let’s organize the solutions in order of increasing values of <math>p</math>, keeping in mind that <math>m</math> and <math>n</math> are bounded between 1 and 30. | ||
+ | |||
+ | For <math>p = 0</math> we get <math>\{1, 5, 9, \ldots, 29\}, \{3, 7, 11, \ldots, 27\}</math>. | ||
+ | |||
+ | For <math>p = 1</math> we get <math>\{2, 10, 18, 26\}, \{6, 14, 22, 30\}</math> | ||
+ | |||
+ | For <math>p = 2</math> we get <math>\{4, 20\}, \{12, 28\}</math> | ||
+ | |||
+ | Note that <math>16\mid{a}</math> since <math>m</math> will cancel out a factor of 4 from <math>a</math>, and <math>\frac{a}{m}</math> must contain a factor of 4. Again, <math>1-4X</math> will never contribute a factor of 2. Simply inspecting, we see two feasible values for <math>a</math> and <math>m</math> such that <math>a+m\leq30</math>. | ||
+ | |||
+ | If we increase the value of <math>p</math> more, there will be less than two integers in our sets, so we are done there. | ||
+ | |||
+ | There are 8 numbers in the first set, 7 in the second, 4 in the third, 4 in the fourth, 2 in the fifth, and 2 in the sixth. | ||
+ | |||
+ | In each of these sets we can choose 2 numbers to be <math>m</math> and <math>n</math> and then assign them in increasing order. Thus there are: | ||
+ | |||
+ | <cmath>\dbinom{8}{2}+\dbinom{7}{2}+\dbinom{4}{2}+\dbinom{4}{2}+\dbinom{2}{2}+\dbinom{2}{2} = 28+21+6+6+1+1 = \boxed{063}</cmath> possible pairs <math>(m,n)</math> that satisfy the conditions. | ||
-KingRavi | -KingRavi | ||
− | ==See | + | ==Solution 3== |
+ | We know that the range of sine is between <math>-1</math> and <math>1</math>, inclusive. | ||
+ | |||
+ | Thus, the only way for the sum to be <math>2</math> is for <math>\sin(mx)=\sin(nx)=1</math>. | ||
+ | |||
+ | Note that <math>\sin(90+360k)=1</math>. | ||
+ | |||
+ | Assuming <math>mx</math> and <math>nx</math> are both positive, <math>m</math> and <math>n</math> could be <math>1,5,9,13,17,21,25,29</math>. There are <math>8</math> ways, so <math>\dbinom{8}{2}</math>. | ||
+ | |||
+ | If both are negative, <math>m</math> and <math>n</math> could be <math>3,7,11,15,19,23,27</math>. There are <math>7</math> ways, so <math>\dbinom{7}{2}</math>. | ||
+ | |||
+ | However, the pair <math>(1,5)</math> could also be <math>(2, 10)</math> and so on. The same goes for some other pairs. | ||
+ | |||
+ | In total there are <math>14</math> of these extra pairs. | ||
+ | |||
+ | The answer is <math>28+21+14 = \boxed{063}</math>. | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | The equation implies that <math>\sin(mx)=\sin(nx)=1</math>. Therefore, we can write <math>mx</math> as <math>2{\pi}k_1+\frac{\pi}{2}</math> and <math>nx</math> as <math>2{\pi}k_2+\frac{\pi}{2}</math> for integers <math>k_1</math> and <math>k_2</math>. Then, <math>\frac{mx}{nx}=\frac{m}{n}=\frac{2k_1+\frac{1}{2}}{2k_2+\frac{1}{2}}</math>. Cross multiplying, we get <math>m\cdot{(2k_2+\frac{1}{2})}=n\cdot{(2k_1+\frac{1}{2})} \Longrightarrow 4k_2m-4k_1n=n-m</math>. Let <math>n-m=a</math> so the equation becomes <math>4(m(k_2-k_1)+k_1a)=a</math>. Let <math>k_2-k_1=X</math> and <math>k_1=Y</math>, then the equation becomes <math>a=4Ym+4Xa \Longrightarrow \frac{a(1-4X)}{m}=4Y</math>. Note that <math>X</math> and <math>Y</math> can vary accordingly, and <math>4\mid{a}</math>. Next, we do casework on <math>m\pmod{4}</math>: | ||
+ | |||
+ | If <math>m\equiv 1\pmod{4}</math>: | ||
+ | |||
+ | Once <math>a</math> and <math>m</math> are determined, <math>n</math> is determined, so <math>a+m\leq30</math>. <math>a\in \{4,8,12,\dots,28\}</math> and <math>m\in \{1,5,9,\dots,29\}</math>. Therefore, there are <math>\sum_{i=1}^{7}{i}=28</math> ways for this case such that <math>a+m\leq30</math>. | ||
+ | |||
+ | If <math>m\equiv 3\pmod{4}</math>: | ||
+ | |||
+ | <math>a\in \{4,8,12,\dots,28\}</math> and <math>m\in \{3,7,11,\dots,27\}</math>. Therefore, there are <math>\sum_{i=1}^{6}{i}=21</math> ways such that <math>a+m\leq30</math>. | ||
+ | |||
+ | If <math>m\equiv 2\pmod{4}</math>: | ||
+ | |||
+ | Note that <math>8\mid{a}</math> since <math>m</math> in this case will have a factor of 2, which will cancel out a factor of 2 in <math>a</math>, and we need the left hand side to divide 4. Also, <math>1-4X\equiv 1\pmod{4}</math> so it is odd and will therefore never contribute a factor of 2. <math>a\in \{8,16,24\}</math> and <math>m\in \{2,6,10,\dots,30\}</math>. Following the condition <math>a+m\leq30</math>, we conclude that there are <math>6+4+2=12</math> ways for this case. | ||
+ | |||
+ | If <math>m\equiv 0\pmod{4}</math>: | ||
+ | |||
+ | Adding all the cases up, we obtain <math>28+21+12+2=\boxed{063}</math> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Magnetoninja Magnetoninja] | ||
+ | |||
+ | ==Remark== | ||
+ | The graphs of <math>r\leq\sin(m\theta)+\sin(n\theta)</math> and <math>r=2</math> are shown here in Desmos: https://www.desmos.com/calculator/busxadywja | ||
+ | |||
+ | Move the sliders around for <math>1\leq m \leq 29</math> and <math>2\leq m+1\leq n\leq30</math> to observe the geometric representation generated by each pair <math>(m,n).</math> | ||
+ | |||
+ | ~MRENTHUSIASM (inspired by TheAMCHub) | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/O84aJ5OTZ2E | ||
+ | |||
+ | ~mathproblemsolvingskills | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=LUkQ7R1DqKo | ||
+ | |||
+ | ~Mathematical Dexterity | ||
+ | |||
+ | ==See Also== | ||
{{AIME box|year=2021|n=I|num-b=6|num-a=8}} | {{AIME box|year=2021|n=I|num-b=6|num-a=8}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 08:12, 3 December 2023
Contents
Problem
Find the number of pairs of positive integers with such that there exists a real number satisfying
Solution 1
It is trivial that the maximum value of is , is achieved at for some integer .
This implies that , and that and , for integers .
Taking their ratio, we have It remains to find all that satisfy this equation.
If , then . This corresponds to choosing two elements from the set . There are ways to do so.
If , by multiplying and by the same constant , we have that . Then either , or . But the first case was already counted, so we don't need to consider that case. The other case corresponds to choosing two numbers from the set . There are ways here. (This argument seems to have a logical flaw)
Finally, if , note that must be an integer. This means that belong to the set , or . Taking casework on , we get the sets . Some sets have been omitted; this is because they were counted in the other cases already. This sums to .
In total, there are pairs of .
This solution was brought to you by ~Leonard_my_dude~
Solution 2
In order for , .
This happens when mod
This means that and for any integers and .
As in Solution 1, take the ratio of the two equations:
Now notice that the numerator and denominator of are both odd, which means that and have the same power of two (the powers of 2 cancel out).
Let the common power be : then , and where and are integers between 1 and 30.
We can now rewrite the equation:
Now it is easy to tell that mod and mod . However, there is another case: that
mod and mod . This is because multiplying both and by will not change the fraction, but each congruence will be changed to mod mod .
From the first set of congruences, we find that and can be two of .
From the second set of congruences, we find that and can be two of .
Now all we have to do is multiply by to get back to and . Let’s organize the solutions in order of increasing values of , keeping in mind that and are bounded between 1 and 30.
For we get .
For we get
For we get
Note that since will cancel out a factor of 4 from , and must contain a factor of 4. Again, will never contribute a factor of 2. Simply inspecting, we see two feasible values for and such that .
If we increase the value of more, there will be less than two integers in our sets, so we are done there.
There are 8 numbers in the first set, 7 in the second, 4 in the third, 4 in the fourth, 2 in the fifth, and 2 in the sixth.
In each of these sets we can choose 2 numbers to be and and then assign them in increasing order. Thus there are:
possible pairs that satisfy the conditions.
-KingRavi
Solution 3
We know that the range of sine is between and , inclusive.
Thus, the only way for the sum to be is for .
Note that .
Assuming and are both positive, and could be . There are ways, so .
If both are negative, and could be . There are ways, so .
However, the pair could also be and so on. The same goes for some other pairs.
In total there are of these extra pairs.
The answer is .
Solution 4
The equation implies that . Therefore, we can write as and as for integers and . Then, . Cross multiplying, we get . Let so the equation becomes . Let and , then the equation becomes . Note that and can vary accordingly, and . Next, we do casework on :
If :
Once and are determined, is determined, so . and . Therefore, there are ways for this case such that .
If :
and . Therefore, there are ways such that .
If :
Note that since in this case will have a factor of 2, which will cancel out a factor of 2 in , and we need the left hand side to divide 4. Also, so it is odd and will therefore never contribute a factor of 2. and . Following the condition , we conclude that there are ways for this case.
If :
Adding all the cases up, we obtain
Remark
The graphs of and are shown here in Desmos: https://www.desmos.com/calculator/busxadywja
Move the sliders around for and to observe the geometric representation generated by each pair
~MRENTHUSIASM (inspired by TheAMCHub)
Video Solution
~mathproblemsolvingskills
Video Solution
https://www.youtube.com/watch?v=LUkQ7R1DqKo
~Mathematical Dexterity
See Also
2021 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
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.