\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{IMO 1988/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 24}
\maketitle
\section*{Problem}
A function $f \colon \NN \to \NN$ is defined by
\begin{align*}
f(1) &= 1, \quad f(3) = 3 \\
f(2n) &= f(n) \\
f(4n+1) &= 2f(2n+1)-f(n) \\
f(4n+3) &= 3f(2n+1)-2f(n)
\end{align*}
for all positive integers $n$.
Determine with proof the number of
positive integers $n \leq 1988$ for which $f(n) = n$.
\section*{Video}
\href{https://www.youtube.com/watch?v=S6igQE958jQ&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/S6igQE958jQ}}
\newpage
\section*{Solution}
The main claim is following.
\begin{claim*}
$f(n)$ is equal to the result when $n$ is written in binary
and its digits are reversed.
\end{claim*}
\begin{proof}
Follows directly by induction.
\end{proof}
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. \]
\end{document}