2021 AIME I Problems/Problem 3
Contents
Problem
Find the number of positive integers less than that can be expressed as the difference of two integral powers of
Solution 1
We want to find the number of positive integers which can be written in the form
for some non-negative integers
(note that if
, then
). We first observe
must be at most 10; if
, then
. As
, we can first choose two different numbers
from the set
in
ways. This includes
,
,
,
,
which are invalid as
in this case. For all other choices
and
, the value of
is less than 1000.
We claim that for all other choices of and
, the values of
are pairwise distinct. More specifically, if
where
and
, we must show that
. Suppose otherwise for sake of contradiction; rearranging yields
. We use the fact that every positive integer has a unique binary representation:
If then
; from here we can deduce either
and
(contradicting the assumption that
, or
and
(contradicting the assumption
and
).
If then
, and it follows that
, also contradicting the assumption
. Hence we obtain contradiction.
Then there are choices for
for which
is a positive integer less than 1000; by the above claim, each choice of
results in a different positive integer
. Then there are
integers which can be expressed as a difference of two powers of 2.
Solution 2 (Casework)
Case 1: When our answer is in the form , where
is an integer such that
.
We start with the subcase where it is , for some integer
where
(this is because the case where
yields
, which doesn't work because it must be a positive integer.)
Note that
, and
. Our answer needs to be less than
, so the maximum possible result (in this case) is
. Our lowest result is
. All the positive powers of two less than
work, so we have
possibilities for this subcase. For subcases
and
, we have
and
possibilities, respectively.
Case 2: When our answer is in the form of , where
is an integer such that
.
We can start with the subcase where . We notice that
, and
which is less than
, so the greatest result in this subcase is actually
, and the lowest is
. Thus, we have
possibilities. For the other four subcases, we have
and
possibilities, respectively.
Answer:
We note that these are our only cases, as numbers in the form of and beyond are greater than
.
Thus, our result is . ~jehu26
Solution 3 (Bash)
We look for all positive integers of the form where
Performing casework on
we can enumerate all possibilities in the table below:
As indicated by the X-marks, the ordered pairs
generate
which are invalid.
Note that each of the remaining ordered pairs generates a unique desired positive integer. We prove as follows:
(1) The positive integers generated in each value of are clearly different.
(2) For all integers the largest positive integer generated for
is
less than the smallest positive integer generated for
Together, we justified our claim in italics. Our answer is
~MRENTHUSIASM
solution 4
First, you need to notice that it is impossible to have overlapping, making the problem easier.
Case 1 :
There are
ways here, from
to
It is easy to see here that this continues all the way down to one. However, when the case gets to , there are 5 ways instead of 4 because
is smaller than 1000.
Thus,
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.