1988 IMO Problems/Problem 3

Problem

A function $f$ defined on the positive integers (and taking positive integers values) is given by:

$\begin{matrix} f(1) = 1, f(3) = 3 \\ f(2 \cdot n) = f(n) \\ f(4 \cdot n + 1) = 2 \cdot f(2 \cdot n + 1) - f(n) \\ f(4 \cdot n + 3) = 3 \cdot f(2 \cdot n + 1) - 2 \cdot f(n), \end{matrix}$

for all positive integers $n.$ Determine with proof the number of positive integers $\leq 1988$ for which $f(n) = n.$

Solution 1

Considering that $f(n)=f(2n)$, the two last equations give : $f(4n + 1)-f(4n) = 2(f(2n + 1) - f(2n))$ $f(4n + 3)-f(4n+2)= 2(f(2n + 1) - f(2n))$

And so, if $n$ is even and $2^{p+1}>n\geq 2^p>1$, we have $f(n+1)-f(n)=2^p$

So, if we have an even $n=\sum_{i=1}^{k} 2^{a_i}$, where $\{a_i\}$ is a strictly increasing sequence with $a_1>0$ ($n$ even) : $f(n+1)=2^{a_k}+f(n)$ Then $f(n)=f(\sum_{i=1}^{k} 2^{a_i})$ $=f(\sum_{i=1}^{k} 2^{a_i-a_1})$ $=2^{a_k-a_1}+f(\sum_{i=2}^{k} 2^{a_i-a_1})$ And so $f((\sum_{i=1}^{k} 2^{a_i})+1)=2^{a_k}+2^{a_k-a_1}+f(\sum_{i=2}^{k} 2^{a_i-a_1})$

And it is easy to conclude that $f(\sum_{i=1}^{k} 2^{a_i})=\sum_{i=1}^{k} 2^{a_k-a_i}$ and that applying $f(n)$ means reversing the order of binary representation of n (and this could be also easily shown with induction).

So $f(n)=n$ occurs if and only if the binary representation of n is symetrical.

It remains to count these "symetric" numbers. We have exactly $2^{\lceil\frac{m-1}{2}\rceil}$ such numbers in $[2^m,2^{m+1})$. So : We have exactly 1 such numbers in $[1,2)$ We have exactly 1 such numbers in $[2,4)$ We have exactly 2 such numbers in $[4,8)$ We have exactly 2 such numbers in $[8,16)$ We have exactly 4 such numbers in $[16,32)$ We have exactly 4 such numbers in $[32,64)$ We have exactly 8 such numbers in $[64,128)$ We have exactly 8 such numbers in $[128,256)$ We have exactly 16 such numbers in $[256,512)$ We have exactly 16 such numbers in $[512,1024)$

Since $1988=B11111000100$, positions 2 to 6 may be any between $00000$ and $11101$, and so : We have exactly 30 such numbers in $[1024,1988]$

And so the requested number is $1+1+2+2+4+4+8+8+16+16+30=92$

This solution was posted and copyrighted by pco. The original thread for this problem can be found here: [1]

Solution 2

The main claim is following.

Claim: $f(n)$ is equal to the result when $n$ is written in binary and its digits are reversed. Proof. Follows directly by induction. $\blacksquare$

So the question asks for the number of binary palindromes which are at most $1988 = 11111000100_2$. For $k = 1, 2, \dots, 10$ there are $2^{\left\lceil k/2 \right\rceil-1}$ binary palindromes with $k$ bits (note the first bit must be $1$). For $k=11$, the number of binary palindromes which are also less than $1988$ is $2^5 - 2$ (only $11111011111$ and $11111111111$ are missing). Hence the final count is\[2^0+2^0 + 2^1+2^1 + 2^2+2^2 + 2^3+2^3 + 2^4+2^4 + (2^5-2) = 92.\]

This solution was posted and copyrighted by v_Enhance. The original thread for this problem can be found here: [2]

Solution 3

We claim that $f(x)$ is the reversal of the digits of $x$ in binary. We proceed by induction, because given $f(1)=f(2)=1$ and $f(3)=3$, we can determine all other values, and this property holds for $f(1)$, $f(2)$, and $f(3)$.

We prove that all operations conserve this property. For $f(2n)=f(n)$, we are adding a zero at the end, thus obviously preserving this property. For $f(4n+1) = 2f(2n+1)-f(n)$, we see that letting $4n+1=\overline{a_1a_2\ldots a_k01}_2$ gets that assuming this holds true for $f(2n+1)$ and $f(n)$, then\[f(4n+1) = 2f(2n+1)-f(n)=2f(\overline{a_1a_2\ldots a_k1}_2)-f(\overline{a_1a_2\ldots a_k}_2)\]\[= 2 \cdot\overline{1a_ka_{k-1}\ldots a_2a_1}_2 - \overline{a_ka_{k-1}\ldots a_2a_1}_2 = \overline{10a_ka_{k-1}\ldots a_2a_1}_2\]which keeps the property since $\overline{10a_ka_{k-1}\ldots a_2a_1}_2$ is the reversal of $\overline{a_1a_2\ldots a_k01}_2$ in binary. Similarly, letting $4n+1=\overline{a_1a_2\ldots a_k11}_2$, then\[f(4n+3) = 3f(2n+1)-2f(n)=3f(\overline{a_1a_2\ldots a_k1}_2)-2f(\overline{a_1a_2\ldots a_k}_2)\]\[= 3 \cdot\overline{1a_ka_{k-1}\ldots a_2a_1}_2 - 2 \cdot \overline{a_ka_{k-1}\ldots a_2a_1}_2 = \overline{11a_ka_{k-1}\ldots a_2a_1}_2\]which keeps the property since $\overline{11a_ka_{k-1}\ldots a_2a_1}_2$ is the reversal of $\overline{a_1a_2\ldots a_k11}_2$. Due to this, we have proved that this property holds for all $n$ which means we need to find the number of binary palindromes below $1988$. This number is just going to be, for $n<11$-digit numbers, $2^{\lfloor \frac {n-1}2 \rfloor}$ ways, so summing up for less than $11$ digits gets $62$ ways. For $11$-digit numbers, we have $32$ ways but need to subtract a few in which are greater than $1988$; there are two numbers we don't count, namely $2015$ and $2047$. As a result, our answer is $62+30=\boxed{92}$.

This solution was posted and copyrighted by kevinmathz. The original thread for this problem can be found here: [3]

See Also

1988 IMO (Problems) • Resources
Preceded by
Problem 2
1 2 3 4 5 6 Followed by
Problem 4
All IMO Problems and Solutions