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 4)
m (→‎See also: also -> Also Case consistency)
(14 intermediate revisions by 3 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{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.
+
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{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{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 a unique desired positive integer.</i> We prove as follows:
+
<b><i>Note that each of the remaining ordered pairs generates one unique desired positive integer.</i></b>
  
−
(1) The positive integers generated in each value of <math>a</math> are clearly different.
+
We prove this statement as follows:
  
−
(2) For all integers <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>
+
<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 italics. Our answer is <cmath>1+2+3+4+5+6+7+8+9+5=\boxed{050}.</cmath>
+
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==
+
==Solution 4==
 
First, you need to notice that it is impossible to have overlapping, making the problem easier.
 
First, you need to notice that it is impossible to have overlapping, making the problem easier.
  
Line 63: Line 72:
 
There are <math>9</math> ways here, from <math>2^1</math> to <math>2^9</math>
 
There are <math>9</math> ways here, from <math>2^1</math> to <math>2^9</math>
  
−
It is easy to see here that this continues all the way down to one. However, when the case gets to <math>32</math>, there are 5 ways instead of 4 because <math>2^10-2^5</math> is smaller than 1000.
+
It is easy to see here that this continues all the way down to one. However, when the case gets to <math>32</math>, there are 5 ways instead of 4 because <math>2^{10}-2^5</math> is smaller than 1000.
  
 
Thus, <math>9+8+7+6+5+5+4+3+2+1 = 50</math>
 
Thus, <math>9+8+7+6+5+5+4+3+2+1 = 50</math>
Line 75: Line 84:
 
https://youtu.be/M3DsERqhiDk?t=749
 
https://youtu.be/M3DsERqhiDk?t=749
  
−
==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}}
  
 
[[Category:Introductory Number Theory Problems]]
 
[[Category:Introductory Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 10:48, 20 June 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 1

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{11}{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{11}{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.


  • 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 $(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$ and $2^{a_1}-2^{b_1} = 2^{a_2} - 2^{b_2}$, for the sake of contradiction. Therefore $\deg_{2}(2^{a_1}-2^{b_1})=\deg_{2}(2^{a_2}-2^{b_2})$, or $b_1=b_2$. Plugging in, we see that $2^{a_1}=2^{a_2}$, or $a_1=a_2$, contradiction.

Note by Ross Gao

Solution 2 (Casework)

Case 1: When our answer is in the form $2^n-2^i$, where $i$ is an integer such that $0\le i\le 4$.

We start with the subcase 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) is $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 subcase. For subcases $i=1, i=2, i=3,$ and $i=4$, we have $8, 7, 6,$ and $5$ possibilities, respectively.

Case 2: When our answer is in the form of $2^n-2^j$, where $j$ is an integer such that $5\le j\le 9$.

We can start with the subcase where $j=5$. We notice that $2^5=32$, and $2^{10}-2^5=992$ which is less than $1000$, so the greatest result in this subcase is actually $2^{10}-2^5$, and the lowest is $2^6-2^5$. Thus, we have $5$ possibilities. For the other four subcases, we have $4, 3, 2,$ and $1$ possibilities, respectively.

Answer: We note 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+5+4+3+2+1=(9+8+7+6+5+4+3+2+1)+5=\boxed{50}$. ~jehu26

Solution 3 (Bash)

We look for all positive integers of the form $2^a-2^b<1000,$ where $0\leq b<a.$ Performing casework on $a,$ we can enumerate all possibilities in the table below: \[\begin{array}{c|c} & \\ [-2.25ex] \boldsymbol{a} & \boldsymbol{b} \\ \hline & \\ [-2ex] 1 & 0 \\ 2 & 0,1 \\ 3 & 0,1,2 \\ 4 & 0,1,2,3 \\ 5 & 0,1,2,3,4 \\ 6 & 0,1,2,3,4,5 \\ 7 & 0,1,2,3,4,5,6 \\ 8 & 0,1,2,3,4,5,6,7 \\ 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 \\ [0.5ex] \end{array}\] As indicated by the X-marks, the ordered pairs $(a,b)=(10,0),(10,1),(10,2),(10,3),(10,4)$ generate $2^a-2^b>1000,$ which are invalid.

Note that each of the remaining ordered pairs generates one unique desired positive integer.

We prove this statement as follows:

  1. The positive integers generated for each value of $a$ are clearly different.

  2. For all integers $k$ such that $1\leq k\leq9,$ the largest positive integer generated for $a=k$ is $1$ less than the smallest positive integer generated for $a=k+1.$

Together, we have justified our claim in bold. The answer is \[1+2+3+4+5+6+7+8+9+5=\boxed{050}.\]

~MRENTHUSIASM

Solution 4

First, you need to notice that it is impossible to have overlapping, making the problem easier.

Case 1 : $2^0$ There are $9$ ways here, from $2^1$ to $2^9$

It is easy to see here that this continues all the way down to one. However, when the case gets to $32$, there are 5 ways instead of 4 because $2^{10}-2^5$ is smaller than 1000.

Thus, $9+8+7+6+5+5+4+3+2+1 = 50$

So the answer is $\boxed{050}$

Video Solution by Punxsutawney Phil

https://youtube.com/watch?v=H17E9n2nIyY&t=569s

Video Solution

https://youtu.be/M3DsERqhiDk?t=749

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