Difference between revisions of "2021 AIME I Problems/Problem 3"
Scrabbler94 (talk | contribs) (more rigorous solution) |
(→Solution) |
||
Line 12: | Line 12: | ||
Then there are <math>\binom{10}{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. | Then there are <math>\binom{10}{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. | ||
+ | |||
+ | ==Solution 2 (Bashy Casework)== | ||
+ | <b>Case 1:</b> We start with the case where it is <math>2^n-2^0</math>, for some integer <math>n</math> where <math>n>0</math> (this is because the case where <math>n=0</math> yields <math>2^0-2^0=0</math>, which doesn't work because it must be a positive integer.) | ||
+ | Note that <math>2^{10}=1024</math>, and <math>2^9=512</math>. Our answer needs to be less than <math>1000</math>, so the maximum possible result (in this case) will be <math>2^9-2^0</math>. Our lowest result is <math>2^1-2^0</math>. All the positive powers of two less than <math>1024</math> work, so we have <math>9</math> possibilities for this case. | ||
+ | |||
+ | <b>Case 2:</b> When our answer is in the form <math>2^n-2^i</math>, where <math>i</math> is an integer such that <math>1\le n\le 4</math>. | ||
+ | Using the same logic as Case 1, we will have <math>8, 7, 6,</math> and <math>5</math> for for <math>i=1, i=2, i=3,</math> and <math>i=4</math>, respectively. | ||
+ | |||
+ | <b>Case 3:</b> When our answer is in the form <math>2^n-2^5</math>. | ||
+ | We notice that <math>2^5=32</math>, and <math>2^{10}-2^5=992</math> which is less than <math>1000</math>, so the greatest result in this case is actually <math>2^{10}-2^5</math>, and the lowest is <math>2^6-2^5</math>. Thus, we have <math>5</math> possibilities. | ||
+ | |||
+ | <b>Case 4:</b> When our answer is in the form of <math>2^n-2^j</math>, where <math>j</math> is an integer such that <math>6\le j\le 9</math>. | ||
+ | Using the same logic as Case 3, we have <math>4, 3, 2,</math> and <math>1</math> for these four subcases. | ||
+ | |||
+ | |||
+ | We notice that these are our only cases, as numbers in the form of <math>2^n-2^{10}</math> and beyond are greater than <math>1000</math>. | ||
+ | |||
+ | Thus, our result is <math>9+8+7+6+5+4+3+2+1+5=\boxed{50}</math>. ~jehu26 | ||
+ | |||
==See also== | ==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}} |
Revision as of 19:49, 11 March 2021
Problem
Find the number of positive integers less than that can be expressed as the difference of two integral powers of
Solution
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.
Solution 2 (Bashy Casework)
Case 1: We start with the case 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) will be . Our lowest result is . All the positive powers of two less than work, so we have possibilities for this case.
Case 2: When our answer is in the form , where is an integer such that . Using the same logic as Case 1, we will have and for for and , respectively.
Case 3: When our answer is in the form . We notice that , and which is less than , so the greatest result in this case is actually , and the lowest is . Thus, we have possibilities.
Case 4: When our answer is in the form of , where is an integer such that . Using the same logic as Case 3, we have and for these four subcases.
We notice that these are our only cases, as numbers in the form of and beyond are greater than .
Thus, our result is . ~jehu26
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.