My Solution for IMO 1988 Problem 3

Question

The problem states:

$\text{ 3. A function f is defined on the positive integers}$$ $$\text{ (and taking positive integer values) is given by }$ $$f(1) = 1, f(3) = 3,$$ $$f(2n) = f(n),$$ $$f(4n + 1) = 2f(2n + 1) - f(n),$$ $$f(4n + 3) = 3f(2n +1) - 2f(n)$$ $\text{for all positive integers n. Determine with proof the}$ $\text{ number of positive integers less than or equal to}$ $\text{ 1988 for which } f(n) = n$

First I have tried to proof $n$ should be even. Then I assumed $f(n) = n$ for all odd positive integers and but such assumption failed because $f(4n + 1) ≠ 4n + 1$. So the remaining set of numbers are odd numbers with difference of four, i.e $f(4n+3)$ pass the test $f(n)= n$. And I got the answer to be quarter of all numbers below 1988 plus $f(1)$. So $498$ is my answer. Can anyone comment on this solution ? Or if I am mistaken, suggest a correction ?This is my first IMO practice question.

Answer 1

Your answer to this problem is not correct (the correct one is $92$); see this video https://youtu.be/eXdUB1wY6d4 where the author uses the fact that the function $f$ reverses the binary rappresentation of $n$.

Answer 2

As said above, $f$ reverses the representation of a number in base $2$. Use induction to prove this claim.

Assume this claim is true for integers less than or equal to $4n$. We are going to prove this for $4n+1$. $4n+1$ is something like $(c_1c_2 ...c_m01)$ in base $2$; one can easily see that $n$ is $(c_1c_2 ...c_m)$ in base $2$ and $2n+1$ is $(c_1c_2 ...c_m1)$. According to the assumption, since both $2n+1$ and $n$ are less than $4n$, we write:$$f(4n+1)=2(1c_mc_{m-1} ...c_1)-(c_mc_{m-1} ...c_1)=(1c_mc_{m-1} ...c_1)+(1c_mc_{m-1} ...c_1)-(c_mc_{m-1} ...c_1)$$

and the last term is equal to $(1c_mc_{m-1} ...c_1)+(10...0)=(10c_mc_{m-1} ...c_1)$. So, in this case induction works.

$4n+3$ is something like $(c_1c_2 ...c_m11)$ in base $2$; one can again easily see that $n$ is $(c_1c_2 ...c_m)$ in base $2$ and $2n+1$ is $(c_1c_2 ...c_m1)$. According to the assumption, since both $2n+1$ and $n$ are less than $4n$, we write:$$f(4n+3)=3(1c_mc_{m-1} ...c_1)-2(c_mc_{m-1} ...c_1)=(1c_mc_{m-1} ...c_1)+(1c_mc_{m-1} ...c_1)+(1c_mc_{m-1} ...c_1)-(c_mc_{m-1} ...c_1)-(c_mc_{m-1} ...c_1)$$

Also,$$ (1c_mc_{m-1} ...c_1)+(1c_mc_{m-1} ...c_1)+(1c_mc_{m-1} ...c_1)-(c_mc_{m-1} ...c_1)-(c_mc_{m-1} ...c_1)$$

is equal to $(1c_mc_{m-1} ...c_1)+(10...0)+(10...0)=(11c_mc_{m-1} ...c_1)$.

In the case $4n+2$ or $4n+4$, they are, respectively, like $(c_1c_2 ...c_m0)$ or $(c_1c_2 ...c_m00)$ in base $2$. Using $f(2n)=f(n)$ confirms that our assumption holds for even numbers as well.

To be done, we should count symmetric numbers in base $2$, such as $(11011)$ or $(10001)$.

Let $a(n)$ denote the number of such numbers with $n$ digits in base $2$, therefore:

$a(1)=1$, $a(2)=1$, $a(3)=2$, $a(4)=2$, $a(5)=4$, $a(6)=4$, $a(7)=8$, $a(8)=8$, $a(9)=16$, $a(10)=16$, $a(11)=32$.

But two of such numbers with $11$ digits in base $2$ are bigger than $1988$. So the answer is $92$.

Answer 3

No, all such numbers doesn't pass the test. For example ,$11=4*2+3$ but $f(11)=13≠11$. There is a beautiful pattern for which $f(n)=n$. All the binary palindromic numbers pass the test, non- palindromic numbers doesn't.

Such that f(1)=1, f(3)=3, ...f(27)=27, ....f(127)=127...$ ,all the numbers $ 1,3, ,27, 127 $....are palindromic.

There are $\sum_{0}^{11} 2^{\lceil \frac{n-2}{2} \rceil } =94 $ such binary Palindromes less than $2048$ ,but $92$ binary Palindromes less than $1988$.

And this function $f(x)$ has a beautiful property to reverse the binary form of any natural number.

This properties can be proven by induction.

Let us assume this reversing property to be true for a set of numbers of some size( that we can prove by hand).

We shall, proof that #$f(2^a+(2*(2k+1))+1)$=#$f(2k+1)$. '#' implies the nature of the number. We have just covered the number $2k+1$ by two $1$s on both sides.

If $2k+1$ is palindromic $(2^a+(2*(2k+1))+1$ is also palindromic, or not when not. And if we can show that $f(f(2^a+(2*(2k+1))+1))=(2^a+(2*(2k+1))+1)$ for $(2k+1)$ palindromiv, then we are done.

See, $f(2^a+(2*(2k+1))+1)=f(4*(2^{a-2}+k)+3)=3*f(2^{a-1}+2k+1)-2*f(2^{a-1}+k)$. It can be proven that k is not palindromic when 2k+1 is except of this (1111111) types. Those can be easily shown with different approach. And, as we are proving with induction, we would assume the reversibility property to be true for $(2^{a-1}+2k+1)$ and others below(less than) this. From reversibility, $f(2^{a-1}+2k+1)=4k+3$ as $2k+1$ is palindromic.

And, $ f(2^{a-2}+k)=4k+3-2^{a-2} $.

Because $2^{a-1}+k$ will be like $11....1$. So, reversing it we get the form $1....11$. Which is the form of $ f(2^{a-1}+k) $. Its very easy to show $1....11=4k+3-2^{a-1}$.

Obviously this is greater than zero, because the highest power of $2$ in $(2k+1)=a-1$. So, we have proved that $f(2^a+2(2k+1)+1)=2^a+2(2k+1)+1$ for $2k+1$ being palindrome.

Similarly we can prove that when $2k+1$ isn't palindromic, $f(2^a+2(2k+1)+1)≠2^a+2(2k+1)+1$. And also we can show that the reversibility property will also be valid in those case. So, by induction we have proved our claim.

The flow of reversibility can be shown by some properties like this... $f(2^{a-1}+2k+1)= 2Rev(2k+1)+1$ and $f(2^{a-2}+k)=2Rev(k)+1$. Now, $Rev(2k+1)=Rev(k)+2^{a-1} $. From here, we can prove the inductive flow of the reversibility property and the ability that only palindromic numbers can only pass $f(n)=n$.