Maths Olympiad Prep

Library / /16 of 61

Algebra Difficulty 5.3 AIME, harder Prove it Ibero-American Mathematical Olympiad

Problem:

The function ff on the positive integers satisfies f(1)=1f(1)=1, f(2n+1)=f(2n)+1f(2n+1)=f(2n)+1 and f(2n)=3f(n)f(2n)=3 f(n). Find the set of all mm such that m=f(n)m=f(n) for some nn.

Solution

Solution:

We show that to obtain f(n)f(n), one writes nn in base 2 and then reads it in base 3. For example, 12=1100212 = 1100_2, so f(12)=11003=36f(12) = 1100_3 = 36. Let g(n)g(n) be defined in this way. Then certainly g(1)=1g(1) = 1. Now 2n+12n+1 has the same binary expansion as 2n2n except for a final 1, so g(2n+1)=g(2n)+1g(2n+1) = g(2n) + 1. Similarly, 2n2n has the same binary expansion as nn with the addition of a final zero. Hence g(2n)=3g(n)g(2n) = 3g(n). So gg is the same as ff. Hence the set of all mm such that m=f(n)m = f(n) for some nn is the set of all mm which can be written in base 3 without a digit 2.

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.