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"

(→‎Solution 2 (More Detailed Explaination))
(more rigorous solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
<math>\binom{11}{2} = 55</math> We need to subtract 5 since <math>2^{10} - 2^0, 2^1, 2^2, 2^3, 2^4</math> don't work. <math>55-5=\boxed{050}</math> ~hansenhe
+
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{10}{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.
  
−
==Solution 2 (More Detailed Explaination)==
+
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:
−
All of the powers of <math>2</math> subtracted by another power of <math>2</math> that can result within 1000 are
 
−
<math>0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024</math> since <math>2048-1024>1000</math>. None of the numbers when chosen two numbers will be the same because the difference of powers of <math>2</math> can be written as a power of two times a non-power of two.
 
  
−
<b><u>Case 1:</u></b> The subtrahend (the second number in a subtraction expression) must be greater than <math>24</math> if the minuend is <math>1024</math>. In this case, the subtrahend can be ranging from <math>32</math> to <math>512</math> giving <math>5</math> total choices.
+
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>).
  
−
<b><u>Case 2:</u></b> If both numbers are powers of two less than <math>1024</math>, then we can choose two numbers from that list and order them to form a positive number. The amount of ways to do this is <math>10\choose2</math> <math>=\frac{10\cdot9}{2}=45</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.
−
In total, there are <math>45+5=\boxed{050}</math> numbers.
 
−
 
 
−
~Interstigation
 
  
 +
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.
 
==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 18:46, 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.

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=149110"