1989 OIM Problems/Problem 5

Problem

Let function $f$ defined over set $\{1,2,3,\ldots\}$ which satisfies

(i) $f(1)=1$

(ii) $f(2n+1)=f(2n)+1$

(iii) $f(2n)=3f(n)$

Find the set of values of $f$.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

We claim that $f$ contains all positive integers which do not include a $2$ in their base $3$ representation.

First, consider (iii) in base $3$. This is just adding a $0$ to the right end of $f(n)$. From there, we can generate our numbers:

From every odd number (say $1$), we use (iii) to add a $0$ to the right end. Then, from (ii), we can choose to either keep it the same (by not applying the property) or changing the end $0$ to a $1$. Notice that this property cannot be applied twice since then $2n+1$ would not be even; thus we must apply (iii) again in order to add another $0$ or $1$, which repeats. As a result, we can continue to add ending digits, and we are able to decide whether they are a $0$ or $1$, which are both of the two remaining legal digits. Thus we can create all values which do not include a $2$ in their base $3$ representation. Clearly, this also does not allow a number with a $2$ in its base $3$ representation; the conclusion follows.

~ eevee9406

See also

https://www.oma.org.ar/enunciados/ibe4.htm