Difference between revisions of "1989 OIM Problems/Problem 5"
(solution) |
|||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Let function <math>f</math> defined over set {1 | + | Let function <math>f</math> defined over set <math>\{1,2,3,\ldots\}</math> which satisfies |
(i) <math>f(1)=1</math> | (i) <math>f(1)=1</math> | ||
| Line 13: | Line 13: | ||
== Solution == | == Solution == | ||
| − | + | We claim that <math>f</math> contains all values which do not include a <math>2</math> in their base <math>3</math> representation. | |
| + | |||
| + | First, consider (iii) in base <math>3</math>. This is just adding a <math>0</math> to the right end of <math>f(n)</math>. From there, we can generate our numbers: | ||
| + | |||
| + | From every odd number (say <math>1</math>), we use (iii) to add a <math>0</math> 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 <math>0</math> to a <math>1</math>. Notice that this property cannot be applied twice since then <math>2n+1</math> would not be even; thus we must apply (iii) again in order to add another <math>0</math> or <math>1</math>, which repeats. As a result, we can continue to add ending digits, and we are able to decide whether they are a <math>0</math> or <math>1</math>, which are both of the two remaining legal digits. Thus we can create all values which do not include a <math>2</math> in their base <math>3</math> representation. Clearly, this also does not allow a number with a <math>2</math> in its base <math>3</math> representation; the conclusion follows. | ||
| + | |||
| + | ~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406] | ||
== See also == | == See also == | ||
https://www.oma.org.ar/enunciados/ibe4.htm | https://www.oma.org.ar/enunciados/ibe4.htm | ||
Revision as of 01:05, 24 March 2025
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 values 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.
