\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{JMO 2013/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 36}
\maketitle
\section*{Problem}
Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$,
where we keep track of the order of the summation.
For example, $f(4)=6$ because $4$ can be written
as $4$, $2+2$, $2+1+1$, $1+2+1$, $1+1+2$, and $1+1+1+1$.
Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.
\section*{Video}
\href{https://www.youtube.com/watch?v=Ewp4nw6Mbr4&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/Ewp4nw6Mbr4}}
\newpage
\section*{Solution}
The answer is $2047$.
For convenience, we agree that $f(0) = 1$.
Then by considering cases on the first number in the representation,
we derive the recurrence
\[ f(n) = \sum_{k=0}^{\left\lfloor \log_2 n \right\rfloor} f(n-2^k).
\qquad (\heartsuit) \]
We wish to understand the parity of $f$. The first few values are
\begin{align*}
f(0) &= 1 \\
f(1) &= 1 \\
f(2) &= 2 \\
f(3) &= 3 \\
f(4) &= 6 \\
f(5) &= 10 \\
f(6) &= 18 \\
f(7) &= 31.
\end{align*}
Inspired by the data we make the key claim that
\begin{claim*}
$f(n)$ is odd if and only if $n+1$ is a power of $2$.
\end{claim*}
\begin{proof}
We call a number \emph{repetitive} if it is zero or its binary representation
consists entirely of $1$'s.
So we want to prove that $f(n)$ is odd if and only if $n$ is repetitive.
This only takes a few cases:
\begin{itemize}
\ii If $n = 2^k$, then $(\heartsuit)$
has exactly two repetitive terms on the right-hand side, namely $0$ and $2^k-1$.
\ii If $n = 2^k + 2^\ell - 1$, then $(\heartsuit)$
has exactly two repetitive terms on the right-hand side,
namely $2^{\ell+1}-1$ and $2^{\ell}-1$.
\ii If $n = 2^k-1$, then $(\heartsuit)$
has exactly one repetitive terms on the right-hand side, namely $2^{k-1}-1$.
\ii For other $n$,
there are no repetitive terms at all on the right-hand side of $(\heartsuit)$.
\end{itemize}
Thus the induction checks out.
\end{proof}
So the final answer to the problem is $2047$.
\end{document}