Maths Olympiad Prep

Library / /5 of 520

Number theory Difficulty 4.5 AIME Find the answer

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We show that to obtain f(n)\mathrm{f}(\mathrm{n}), one writes n\mathrm{n} in base 2 and then reads it in base 3. For example 12 =11002=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+12 n+1 has the same binary expansion as 2n2 n except for a final 1, so g(2n+1)=g(2n)+1g(2 n+1)=g(2 n)+1. Similarly, 2n2 \mathrm{n} has the same binary expansion as n\mathrm{n} with the addition of a final zero. Hence g(2n)=3g(n)g(2 n)=3 g(n). So gg is the same as f. Hence the set of all mm such that m=f(n)m=f(n) for some nn is the the set of all m\mathrm{m} 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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.