Maths Olympiad Prep

Library / /36 of 48

Algebra Difficulty 5.0 AIME Prove it United States

Problem:

An integer is called formidable if it can be written as a sum of distinct powers of 44, and successful if it can be written as a sum of distinct powers of 66. Can 20052005 be written as a sum of a formidable number and a successful number? Prove your answer.

Solution

Solution:

Suppose that 2005=a+b2005 = a + b, where aa is formidable and bb is successful. Then aa must be a sum of some of the powers of 44 less than 20052005, namely 1,4,16,64,256,10241, 4, 16, 64, 256, 1024. Similarly, bb must be a sum of some of the numbers 1,6,36,216,12961, 6, 36, 216, 1296. So, a+ba + b must be a sum of some distinct entries from the list
1,1,4,6,16,36,64,216,256,1024,1296. 1, 1, 4, 6, 16, 36, 64, 216, 256, 1024, 1296.
If we use both 10241024 and 12961296, we get at least 1024+1296=23201024 + 1296 = 2320 which is too big. But if we omit one of them, the most we can get is
1+1+4+6+16+36+64+216+256+1296=1896 1 + 1 + 4 + 6 + 16 + 36 + 64 + 216 + 256 + 1296 = 1896
which is too small. So there is no way to achieve a sum of 20052005.

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.