2021 AIME I Problems/Problem 3
Find the number of positive integers less than that can be expressed as the difference of two integral powers of
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.
|2021 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|