Difference between revisions of "2021 AIME I Problems/Problem 3"
(→solution 4) |
|||
(20 intermediate revisions by 6 users not shown) | |||
Line 3: | Line 3: | ||
==Solution 1== | ==Solution 1== | ||
− | We want to find the number of positive integers <math>n<1000</math> which can be written in the form <math>n = 2^a - 2^b</math> for some non-negative integers <math>a > b \ge 0</math> (note that if <math>a=b</math>, then <math>2^a-2^b = 0</math>). We first observe <math>a</math> must be at most 10; if <math>a \ge 11</math>, then <math>2^a - 2^b \ge 2^{10} > 1000</math>. As <math>2^{10} = 1024 \approx 1000</math>, we can first choose two different numbers <math>a > b</math> from the set <math>\{0,1,2,\ldots,10\}</math> in <math>\binom{ | + | We want to find the number of positive integers <math>n<1000</math> which can be written in the form <math>n = 2^a - 2^b</math> for some non-negative integers <math>a > b \ge 0</math> (note that if <math>a=b</math>, then <math>2^a-2^b = 0</math>). We first observe <math>a</math> must be at most 10; if <math>a \ge 11</math>, then <math>2^a - 2^b \ge 2^{10} > 1000</math>. As <math>2^{10} = 1024 \approx 1000</math>, we can first choose two different numbers <math>a > b</math> from the set <math>\{0,1,2,\ldots,10\}</math> in <math>\binom{11}{2}=55</math> ways. This includes <math>(a,b) = (10,0)</math>, <math>(10,1)</math>, <math>(10,2)</math>, <math>(10,3)</math>, <math>(10,4)</math> which are invalid as <math>2^a - 2^b > 1000</math> in this case. For all other choices <math>a</math> and <math>b</math>, the value of <math>2^a - 2^b</math> is less than 1000. |
We claim that for all other choices of <math>a</math> and <math>b</math>, the values of <math>2^a - 2^b</math> are pairwise distinct. More specifically, if <math>(a_1,b_1) \neq (a_2,b_2)</math> where <math>10 \ge a_1 > b_1 \ge 0</math> and <math>10 \ge a_2 > b_2 \ge 0</math>, we must show that <math>2^{a_1}-2^{b_1} \neq 2^{a_2} - 2^{b_2}</math>. Suppose otherwise for sake of contradiction; rearranging yields <math>2^{a_1}+2^{b_2} = 2^{a_2}+2^{b_1}</math>. We use the fact that every positive integer has a unique binary representation: | We claim that for all other choices of <math>a</math> and <math>b</math>, the values of <math>2^a - 2^b</math> are pairwise distinct. More specifically, if <math>(a_1,b_1) \neq (a_2,b_2)</math> where <math>10 \ge a_1 > b_1 \ge 0</math> and <math>10 \ge a_2 > b_2 \ge 0</math>, we must show that <math>2^{a_1}-2^{b_1} \neq 2^{a_2} - 2^{b_2}</math>. Suppose otherwise for sake of contradiction; rearranging yields <math>2^{a_1}+2^{b_2} = 2^{a_2}+2^{b_1}</math>. We use the fact that every positive integer has a unique binary representation: | ||
Line 9: | Line 9: | ||
If <math>a_1 \neq b_2</math> then <math>\{a_1,b_2\} = \{a_2,b_1\}</math>; from here we can deduce either <math>a_1=a_2</math> and <math>b_1=b_2</math> (contradicting the assumption that <math>(a_1,b_1) \neq (a_2,b_2)</math>, or <math>a_1=b_1</math> and <math>a_2=b_2</math> (contradicting the assumption <math>a_1>b_1</math> and <math>a_2>b_2</math>). | If <math>a_1 \neq b_2</math> then <math>\{a_1,b_2\} = \{a_2,b_1\}</math>; from here we can deduce either <math>a_1=a_2</math> and <math>b_1=b_2</math> (contradicting the assumption that <math>(a_1,b_1) \neq (a_2,b_2)</math>, or <math>a_1=b_1</math> and <math>a_2=b_2</math> (contradicting the assumption <math>a_1>b_1</math> and <math>a_2>b_2</math>). | ||
− | If <math>a_1 = b_2</math> then <math>2^{a_1}+2^{b_2} = 2 \times 2^{a_1}</math>, and it follows that <math>a_1=a_2=b_1=b_2</math>, also contradicting the assumption <math>(a_1,b_1) \neq (a_2,b_2)</math>. Hence we obtain contradiction. | + | If <math>a_1 = b_2</math> then <math>2^{a_1}+2^{b_2} = 2 \times 2^{a_1}</math>, and it follows that <math>a_1=a_2=b_1=b_2</math>, also contradicting the assumption <math>(a_1,b_1) \neq (a_2,b_2)</math>. Hence we obtain contradiction.* |
− | Then there are <math>\binom{ | + | Then there are <math>\binom{11}{2}-5</math> choices for <math>(a,b)</math> for which <math>2^a - 2^b</math> is a positive integer less than 1000; by the above claim, each choice of <math>(a,b)</math> results in a different positive integer <math>n</math>. Then there are <math>55-5 = \boxed{050}</math> integers which can be expressed as a difference of two powers of 2. |
+ | |||
+ | |||
+ | *Note: The uniqueness of binary representation could be rather easily proven, but if you cannot convince yourself on the spot that this is the case, consider the following alternative proof. Let <math>(a_1,b_1) \neq (a_2,b_2)</math> where <math>10 \ge a_1 > b_1 \ge 0</math> and <math>10 \ge a_2 > b_2 \ge 0</math> and <math>2^{a_1}-2^{b_1} = 2^{a_2} - 2^{b_2}</math>, for the sake of contradiction. Therefore <math>\deg_{2}(2^{a_1}-2^{b_1})=\deg_{2}(2^{a_2}-2^{b_2})</math>, or <math>b_1=b_2</math>. Plugging in, we see that <math>2^{a_1}=2^{a_2}</math>, or <math>a_1=a_2</math>, contradiction. | ||
+ | |||
+ | Note by Ross Gao | ||
==Solution 2 (Casework)== | ==Solution 2 (Casework)== | ||
Line 31: | Line 36: | ||
We look for all positive integers of the form <math>2^a-2^b<1000,</math> where <math>0\leq b<a.</math> Performing casework on <math>a,</math> we can enumerate all possibilities in the table below: | We look for all positive integers of the form <math>2^a-2^b<1000,</math> where <math>0\leq b<a.</math> Performing casework on <math>a,</math> we can enumerate all possibilities in the table below: | ||
<cmath>\begin{array}{c|c} | <cmath>\begin{array}{c|c} | ||
+ | & \\ [-2.25ex] | ||
\boldsymbol{a} & \boldsymbol{b} \\ | \boldsymbol{a} & \boldsymbol{b} \\ | ||
\hline | \hline | ||
Line 43: | Line 49: | ||
8 & 0,1,2,3,4,5,6,7 \\ | 8 & 0,1,2,3,4,5,6,7 \\ | ||
9 & 0,1,2,3,4,5,6,7,8 \\ | 9 & 0,1,2,3,4,5,6,7,8 \\ | ||
− | 10 & \xcancel{0},\xcancel{1},\xcancel{2},\xcancel{3},\xcancel{4},5,6,7,8,9 | + | 10 & \xcancel{0},\xcancel{1},\xcancel{2},\xcancel{3},\xcancel{4},5,6,7,8,9 \\ [0.5ex] |
\end{array}</cmath> | \end{array}</cmath> | ||
As indicated by the X-marks, the ordered pairs <math>(a,b)=(10,0),(10,1),(10,2),(10,3),(10,4)</math> generate <math>2^a-2^b>1000,</math> which are invalid. | As indicated by the X-marks, the ordered pairs <math>(a,b)=(10,0),(10,1),(10,2),(10,3),(10,4)</math> generate <math>2^a-2^b>1000,</math> which are invalid. | ||
− | <i>Note that each of the remaining ordered pairs generates | + | <b><i>Note that each of the remaining ordered pairs generates one unique desired positive integer.</i></b> |
− | + | We prove this statement as follows: | |
− | + | <ol style="margin-left: 1.5em;"> | |
+ | <li>The positive integers generated for each value of <math>a</math> are clearly different.</li><p> | ||
+ | <li>For all integers <math>k</math> such that <math>1\leq k\leq9,</math> the largest positive integer generated for <math>a=k</math> is <math>1</math> less than the smallest positive integer generated for <math>a=k+1.</math></li><p> | ||
+ | </ol> | ||
− | Together, we justified our claim in | + | Together, we have justified our claim in bold. The answer is <cmath>1+2+3+4+5+6+7+8+9+5=\boxed{050}.</cmath> |
~MRENTHUSIASM | ~MRENTHUSIASM | ||
− | == | + | ==Solution 4 (Faster Way)== |
− | + | Because the difference is less than <math>1000</math>, we can simply list out all numbers that satisfy <math>2^n < 1000</math>. We get <math>0 \le n < 10</math>, where n is an integer. Because the sequence <math>2^n</math> is geometric, the difference of any two terms will be unique. <math>\binom{10}{2}</math> will be the number of differences for <math>0\le n < 10</math>. However, we also need to consider the case in which <math>n=10</math>. With simple counting, we find that <math>5</math> numbers: <math>(32, 64, 128, 256, 512)</math> could be subtracted from <math>1024</math>, which makes another 5 cases. There is no need to check for higher exponents since the lowest difference would be <math>2^{11} - 2^{10} = 1024</math>, which exceeds <math>1000</math>. | |
− | + | Thus, the final answer is <math>\binom{10}{2} + 5 = \boxed{050}.</math> | |
− | |||
− | + | ~TOMYANG | |
− | |||
− | |||
==Video Solution by Punxsutawney Phil== | ==Video Solution by Punxsutawney Phil== | ||
Line 73: | Line 79: | ||
https://youtu.be/M3DsERqhiDk?t=749 | https://youtu.be/M3DsERqhiDk?t=749 | ||
− | ==See | + | ==Video Solution by Power of Logic== |
+ | https://youtu.be/FdB0XMlVC7A | ||
+ | |||
+ | ==Video Solution by WhyMath== | ||
+ | https://youtu.be/7q83bqTP7Qg | ||
+ | |||
+ | ~savannahsolver | ||
+ | |||
+ | ==See Also== | ||
{{AIME box|year=2021|n=I|num-b=2|num-a=4}} | {{AIME box|year=2021|n=I|num-b=2|num-a=4}} | ||
[[Category:Introductory Number Theory Problems]] | [[Category:Introductory Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 08:21, 13 May 2023
Contents
Problem
Find the number of positive integers less than that can be expressed as the difference of two integral powers of
Solution 1
We want to find the number of positive integers which can be written in the form for some non-negative integers (note that if , then ). We first observe must be at most 10; if , then . As , we can first choose two different numbers from the set in ways. This includes , , , , which are invalid as in this case. For all other choices and , the value of is less than 1000.
We claim that for all other choices of and , the values of are pairwise distinct. More specifically, if where and , we must show that . Suppose otherwise for sake of contradiction; rearranging yields . We use the fact that every positive integer has a unique binary representation:
If then ; from here we can deduce either and (contradicting the assumption that , or and (contradicting the assumption and ).
If then , and it follows that , also contradicting the assumption . Hence we obtain contradiction.*
Then there are choices for for which is a positive integer less than 1000; by the above claim, each choice of results in a different positive integer . Then there are integers which can be expressed as a difference of two powers of 2.
- Note: The uniqueness of binary representation could be rather easily proven, but if you cannot convince yourself on the spot that this is the case, consider the following alternative proof. Let where and and , for the sake of contradiction. Therefore , or . Plugging in, we see that , or , contradiction.
Note by Ross Gao
Solution 2 (Casework)
Case 1: When our answer is in the form , where is an integer such that .
We start with the subcase where it is , for some integer where (this is because the case where yields , which doesn't work because it must be a positive integer.) Note that , and . Our answer needs to be less than , so the maximum possible result (in this case) is . Our lowest result is . All the positive powers of two less than work, so we have possibilities for this subcase. For subcases and , we have and possibilities, respectively.
Case 2: When our answer is in the form of , where is an integer such that .
We can start with the subcase where . We notice that , and which is less than , so the greatest result in this subcase is actually , and the lowest is . Thus, we have possibilities. For the other four subcases, we have and possibilities, respectively.
Answer: We note that these are our only cases, as numbers in the form of and beyond are greater than .
Thus, our result is . ~jehu26
Solution 3 (Bash)
We look for all positive integers of the form where Performing casework on we can enumerate all possibilities in the table below: As indicated by the X-marks, the ordered pairs generate which are invalid.
Note that each of the remaining ordered pairs generates one unique desired positive integer.
We prove this statement as follows:
- The positive integers generated for each value of are clearly different.
- For all integers such that the largest positive integer generated for is less than the smallest positive integer generated for
Together, we have justified our claim in bold. The answer is
~MRENTHUSIASM
Solution 4 (Faster Way)
Because the difference is less than , we can simply list out all numbers that satisfy . We get , where n is an integer. Because the sequence is geometric, the difference of any two terms will be unique. will be the number of differences for . However, we also need to consider the case in which . With simple counting, we find that numbers: could be subtracted from , which makes another 5 cases. There is no need to check for higher exponents since the lowest difference would be , which exceeds .
Thus, the final answer is
~TOMYANG
Video Solution by Punxsutawney Phil
https://youtube.com/watch?v=H17E9n2nIyY&t=569s
Video Solution
https://youtu.be/M3DsERqhiDk?t=749
Video Solution by Power of Logic
Video Solution by WhyMath
~savannahsolver
See Also
2021 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
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.