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

m (Solution 3 (Bash): Centered the third column in the table.)
m (See also: also -> Also Case consistency)
(31 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{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)==
 
<b>Case 1:</b> When our answer is in the form <math>2^n-2^i</math>, where <math>i</math> is an integer such that <math>0\le i\le 4</math>.  
 
<b>Case 1:</b> When our answer is in the form <math>2^n-2^i</math>, where <math>i</math> is an integer such that <math>0\le i\le 4</math>.  
 +
 
We start with the subcase 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.)  
 
We start with the subcase 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) is <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 subcase. For subcases <math>i=1, i=2, i=3,</math> and <math>i=4</math>, we have <math>8, 7, 6,</math> and <math>5</math> possibilities, respectively.
 
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) is <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 subcase. For subcases <math>i=1, i=2, i=3,</math> and <math>i=4</math>, we have <math>8, 7, 6,</math> and <math>5</math> possibilities, respectively.
  
 
<b>Case 2:</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>5\le j\le 9</math>.
 
<b>Case 2:</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>5\le j\le 9</math>.
 +
 
We can start with the subcase where <math>j=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 subcase 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. For the other four subcases, we have <math>4, 3, 2,</math> and <math>1</math> possibilities, respectively.
 
We can start with the subcase where <math>j=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 subcase 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. For the other four subcases, we have <math>4, 3, 2,</math> and <math>1</math> possibilities, respectively.
  
 +
<b>Answer:</b>
 
We note 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>.  
 
We note 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>.  
  
Line 27: Line 35:
 
==Solution 3 (Bash)==
 
==Solution 3 (Bash)==
 
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|c}
+
<cmath>\begin{array}{c|c}
\textbf{Case} & \boldsymbol{a} & \boldsymbol{b} \\  
+
& \\ [-2.25ex]
 +
\boldsymbol{a} & \boldsymbol{b} \\  
 
\hline  
 
\hline  
& & \\ [-2ex]
+
& \\ [-2ex]
1 & 1 & 0 \\   
+
1 & 0 \\   
2 & 2 & 0,1 \\
+
2 & 0,1 \\
3 & 3 & 0,1,2 \\
+
3 & 0,1,2 \\
4 & 4 & 0,1,2,3 \\
+
4 & 0,1,2,3 \\
5 & 5 & 0,1,2,3,4 \\
+
5 & 0,1,2,3,4 \\
6 & 6 & 0,1,2,3,4,5 \\
+
6 & 0,1,2,3,4,5 \\
7 & 7 & 0,1,2,3,4,5,6 \\
+
7 & 0,1,2,3,4,5,6 \\
8 & 8 & 0,1,2,3,4,5,6,7 \\
+
8 & 0,1,2,3,4,5,6,7 \\
9 & 9 & 0,1,2,3,4,5,6,7,8 \\
+
9 & 0,1,2,3,4,5,6,7,8 \\
10 & 10 & \underline{0},\underline{1},\underline{2},\underline{3},\underline{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 underlined, 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 case are clearly different.
+
We prove this statement as follows:
  
(2) For all integers <math>1\leq k\leq9,</math> the largest positive integer generated in Case <math>k</math> is <math>1</math> less than the smallest positive integer generated in Case <math>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==
 +
First, you need to notice that it is impossible to have overlapping, making the problem easier.
 +
 +
Case 1 : <math>2^0</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.
 +
 +
Thus, <math>9+8+7+6+5+5+4+3+2+1 = 50</math>
 +
 +
So the answer is <math>\boxed{050}</math>
  
 
==Video Solution by Punxsutawney Phil==
 
==Video Solution by Punxsutawney Phil==
 
https://youtube.com/watch?v=H17E9n2nIyY&t=569s
 
https://youtube.com/watch?v=H17E9n2nIyY&t=569s
  
==See also==
+
==Video Solution==
 +
https://youtu.be/M3DsERqhiDk?t=749
 +
 
 +
==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 (ProblemsAnswer KeyResources)
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