Maths Olympiad Prep

Library / /2 of 8

Algebra Difficulty 5.8 AIME, harder Prove it Romania

How many of the first 2017 positive integers can be uniquely represented as 2a+2b+2c2^a + 2^b + 2^c, with aa, bb, cc non-negative integers? (Two representations that only differ by the order of the terms are considered identical.)

Solution

If a number can be represented as a sum of three, not necessarily distinct, powers of 22, regrouping the equal terms (if such terms exist), one obtains a sum of at most three distinct powers of 22, hence the base 22 representation of such a number has at most three digits equal to 11. Convenient numbers are those whose base 22 representation have three digits equal to 11, then the numbers of the form 2a+1=2a1+2a1+12^a + 1 = 2^{a-1} + 2^{a-1} + 1 with aNa \in \mathbb{N} (numbers 2a+2b2^a + 2^b with a>b1a > b \ge 1 are not convenient because 2a+2b=2a1+2a1+2b=2b1+2b1+2a2^a + 2^b = 2^{a-1} + 2^{a-1} + 2^b = 2^{b-1} + 2^{b-1} + 2^a); finally, the numbers 2c=2c1+2c1+2c22^c = 2^{c-1} + 2^{c-1} + 2^{c-2} are also convenient if c2c \ge 2.

Let us count first the convenient numbers that are less than 20482048. The base 22 representation of these numbers has at most 1111 digits. There are C113=165C_{11}^3 = 165 numbers less than 20482048 that can be written as a sum of three distinct powers of 22. There are 1010 numbers of the form 2a+12^a + 1, (1a10)(1 \le a \le 10) and 99 of the form 2a2^a (2a10)(2 \le a \le 10), hence 184184 numbers in total.

The numbers from 20182018 to 20472047 are larger than 210+29+282^{10} + 2^9 + 2^8, hence their base 22 representation has more than three digits equal to 11, therefore none of these numbers is convenient. In conclusion, there are 184184 convenient numbers among the first 20172017.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.