Kvant Math Problem 1132
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m47s
Source on kvant.digital
Problem
The function $f$ is defined on the set of positive integers and satisfies the following conditions: $$\begin{gathered} f(1)=1,\quad f(3)=3,\quad f(2n)=f(n),\ f(4n+1)=2f(2n+1)-f(n),\quad f(4n+3)=3f(2n+1)-2f(n) \end{gathered}$$. Find the number of all such values $n$ for which $f(n)=n$ and $1\le n\le 1988$.
International Mathematical Olympiad for School Students (XXIX)
Exploration
Let
$$e(n)=f(n)-n.$$
Substituting the defining relations gives
$$e(2n)=e(n)-n,$$
and for odd arguments
$$e(4n+1)=2e(2n+1)-e(n), \qquad e(4n+3)=3e(2n+1)-2e(n).$$
The nonhomogeneous terms disappear. This suggests that the function is related to a digit operation rather than to ordinary arithmetic growth.
Computing several values,
$$f(1)=1,\quad f(3)=3,\quad f(5)=5,\quad f(7)=7,\quad f(9)=9,$$
but
$$f(11)=13,\qquad f(13)=11,$$
and
$$f(19)=25,\qquad f(25)=19.$$
Writing these numbers in binary,
$$11=(1011)_2,\qquad 13=(1101)_2,$$
$$19=(10011)_2,\qquad 25=(11001)_2.$$
Each image is obtained by reversing the binary digits.
This conjecture also matches even numbers:
$$10=(1010)_2 \mapsto (0101)_2=5,$$
and indeed $f(10)=5$.
The crucial point is to prove that the binary reversal function satisfies exactly the same recurrence relations as $f$. Once this is established, induction gives $f$ uniquely. Then $f(n)=n$ becomes the condition that the binary representation of $n$ is a palindrome.
Problem Understanding
We are given a recursively defined function $f$ on the positive integers. We must determine how many integers $n$ with
$$1\le n\le 1988$$
satisfy
$$f(n)=n.$$
This is a Type C problem, because the required output is a numerical value.
The core difficulty is identifying the function hidden behind the recurrences. After recognizing that $f$ is binary digit reversal, the condition $f(n)=n$ becomes a counting problem for binary palindromes.
The answer will be $92$. Binary reversal fixes exactly the binary palindromes, and the number of binary palindromes not exceeding $1988$ turns out to be $92$.
Proof Architecture
Define $R(n)$ to be the integer obtained by reversing the binary representation of $n$; the first lemma states that $R$ satisfies the same recurrences as $f$.
The second lemma states that $f(n)=R(n)$ for all positive integers; it follows by strong induction because the recurrences express the value at $n$ through values at smaller arguments.
The third lemma states that $f(n)=n$ if and only if the binary representation of $n$ is a palindrome; this follows immediately from the interpretation as binary reversal.
The final step counts binary palindromes of lengths at most $10$, then counts those of length $11$ that do not exceed $1988$.
The most delicate lemma is the first one, because the recurrence must be derived exactly from the effect of appending binary digits and then reversing them.
Solution
For every positive integer $n$, let $R(n)$ denote the integer obtained by reversing the binary representation of $n$.
For example,
$$R(11)=R((1011)_2)=(1101)_2=13.$$
We first prove that $R$ satisfies the same recurrence relations as $f$.
Let the binary representation of $k$ be a word $A$ of length $t$. Let $A^R$ denote the reversed word. Then
$$R(k)=\operatorname{val}(A^R).$$
The binary representation of $2k+1$ is $A1$. Hence
$$R(2k+1)=\operatorname{val}(1A^R)=2^t+R(k).$$
Now consider $4k+1$. Its binary representation is $A01$. Reversing gives
$$R(4k+1)=\operatorname{val}(10A^R)=2^{t+1}+R(k).$$
Using $R(2k+1)=2^t+R(k)$,
$$2R(2k+1)-R(k) =2(2^t+R(k))-R(k) =2^{t+1}+R(k) =R(4k+1).$$
Similarly, $4k+3$ has binary representation $A11$. Reversing gives
$$R(4k+3)=\operatorname{val}(11A^R)=3\cdot 2^t+R(k).$$
Therefore
$$3R(2k+1)-2R(k) =3(2^t+R(k))-2R(k) =3\cdot 2^t+R(k) =R(4k+3).$$
Finally, reversing the binary representation of $2n$ removes the trailing zero, so
$$R(2n)=R(n).$$
Also,
$$R(1)=1,\qquad R(3)=3.$$
Thus $R$ satisfies exactly the same defining relations as $f$.
We now prove that
$$f(n)=R(n)$$
for all positive integers $n$.
The statement is true for $n=1$ and $n=3$.
Assume it