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]

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

Page

Toolbox

Search

1988 IMO Problems/Problem 3

Contents

Problem

Solution 1

Solution 2

Solution 3

See Also