1989 OIM Problems/Problem 5
Problem
Let function defined over set
which satisfies
(i)
(ii)
(iii)
Find the set of values of .
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
We claim that contains all positive integers which do not include a
in their base
representation.
First, consider (iii) in base . This is just adding a
to the right end of
. From there, we can generate our numbers:
From every odd number (say ), we use (iii) to add a
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
to a
. Notice that this property cannot be applied twice since then
would not be even; thus we must apply (iii) again in order to add another
or
, which repeats. As a result, we can continue to add ending digits, and we are able to decide whether they are a
or
, which are both of the two remaining legal digits. Thus we can create all values which do not include a
in their base
representation. Clearly, this also does not allow a number with a
in its base
representation; the conclusion follows.