Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 AIME I Problems/Problem 3"

(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 $1000$ that can be expressed as the difference of two integral powers of $2.$

Solution

We want to find the number of positive integers $n<1000$ which can be written in the form $n = 2^a - 2^b$ for some non-negative integers $a > b \ge 0$ (note that if $a=b$, then $2^a-2^b = 0$). We first observe $a$ must be at most 10; if $a \ge 11$, then $2^a - 2^b \ge 2^{10} > 1000$. As $2^{10} = 1024 \approx 1000$, we can first choose two different numbers $a > b$ from the set $\{0,1,2,\ldots,10\}$ in $\binom{10}{2}=55$ ways. This includes $(a,b) = (10,0)$, $(10,1)$, $(10,2)$, $(10,3)$, $(10,4)$ which are invalid as $2^a - 2^b > 1000$ in this case. For all other choices $a$ and $b$, the value of $2^a - 2^b$ is less than 1000.

We claim that for all other choices of $a$ and $b$, the values of $2^a - 2^b$ are pairwise distinct. More specifically, if $(a_1,b_1) \neq (a_2,b_2)$ where $10 \ge a_1 > b_1 \ge 0$ and $10 \ge a_2 > b_2 \ge 0$, we must show that $2^{a_1}-2^{b_1} \neq 2^{a_2} - 2^{b_2}$. Suppose otherwise for sake of contradiction; rearranging yields $2^{a_1}+2^{b_2} = 2^{a_2}+2^{b_1}$. We use the fact that every positive integer has a unique binary representation:

If $a_1 \neq b_2$ then $\{a_1,b_2\} = \{a_2,b_1\}$; from here we can deduce either $a_1=a_2$ and $b_1=b_2$ (contradicting the assumption that $(a_1,b_1) \neq (a_2,b_2)$, or $a_1=b_1$ and $a_2=b_2$ (contradicting the assumption $a_1>b_1$ and $a_2>b_2$).

If $a_1 = b_2$ then $2^{a_1}+2^{b_2} = 2 \times 2^{a_1}$, and it follows that $a_1=a_2=b_1=b_2$, also contradicting the assumption $(a_1,b_1) \neq (a_2,b_2)$. Hence we obtain contradiction.

Then there are $\binom{10}{2}-5$ choices for $(a,b)$ for which $2^a - 2^b$ is a positive integer less than 1000; by the above claim, each choice of $(a,b)$ results in a different positive integer $n$. Then there are $55-5 = \boxed{050}$ 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 $2^n-2^0$, for some integer $n$ where $n>0$ (this is because the case where $n=0$ yields $2^0-2^0=0$, which doesn't work because it must be a positive integer.) Note that $2^{10}=1024$, and $2^9=512$. Our answer needs to be less than $1000$, so the maximum possible result (in this case) will be $2^9-2^0$. Our lowest result is $2^1-2^0$. All the positive powers of two less than $1024$ work, so we have $9$ possibilities for this case.

Case 2: When our answer is in the form $2^n-2^i$, where $i$ is an integer such that $1\le n\le 4$. Using the same logic as Case 1, we will have $8, 7, 6,$ and $5$ for for $i=1, i=2, i=3,$ and $i=4$, respectively.

Case 3: When our answer is in the form $2^n-2^5$. We notice that $2^5=32$, and $2^{10}-2^5=992$ which is less than $1000$, so the greatest result in this case is actually $2^{10}-2^5$, and the lowest is $2^6-2^5$. Thus, we have $5$ possibilities.

Case 4: When our answer is in the form of $2^n-2^j$, where $j$ is an integer such that $6\le j\le 9$. Using the same logic as Case 3, we have $4, 3, 2,$ and $1$ for these four subcases.


We notice that these are our only cases, as numbers in the form of $2^n-2^{10}$ and beyond are greater than $1000$.

Thus, our result is $9+8+7+6+5+4+3+2+1+5=\boxed{50}$. ~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_3&oldid=149111"