Maths Olympiad Prep

Library / /68 of 94

Number theory Difficulty 5.1 AIME, harder Prove it United States

Problem:

Call a positive integer "mild" if its base-3 representation never contains the digit 22. How many values of nn (1n10001 \leq n \leq 1000) have the property that nn and n2n^{2} are both mild?

Solution

Solution:

Such a number, which must consist entirely of 00's and 11's in base 33, can never have more than one 11. Indeed, if n=3a+3b+n = 3^{a} + 3^{b} + higher powers where b>ab > a, then n2=32a+23a+b+n^{2} = 3^{2a} + 2 \cdot 3^{a+b} + higher powers which will not be mild. On the other hand, if nn does just have one 11 in base 33, then clearly nn and n2n^{2} are mild. So the values of n1000n \leq 1000 that work are 30,31,,363^{0}, 3^{1}, \ldots, 3^{6}; there are 77 of them.

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.