2021 AIME I Problems/Problem 3

Problem

Find the number of positive integers less than $1000$ that can be expressed as the difference of two integral powers of $2.$

Solution

$\binom{11}{2} = 55$ We need to subtract 5 since $2^{10} - 2^0, 2^1, 2^2, 2^3, 2^4$ don't work. $55-5=\boxed{050}$ ~hansenhe

Solution 2 (More detailed explaination)

All of the powers of $2$ subtracted by another power of $2$ that can result within 1000 is listed: $0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$ since $2048-1024>1000$ . None of the numbers when chosen two numbers will be the same because the difference of powers of $2$ can be written as a power of two times a non-power of two. Case 1: The subtrahend (the second number in a subtraction expression) must be greater than $24$ if the minuend is $1024$ . In this case, the subtrahend can be ranging from $32$ to $512$ giving $5$ total choices. Case 2: If both numbers are powers of two less than $1024$ , 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 $10\choose2$ $=45$ . In total, there are $45+5=\boxed{050}$ numbers.

~Interstigation

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

Page

Toolbox

Search

2021 AIME I Problems/Problem 3

Contents

Problem

Solution

Solution 2 (More detailed explaination)

See also