\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USEMO 2022/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 103}
\maketitle

\section*{Problem}
Find all positive integers $k$ for which there
exists a \emph{nonlinear} function $f \colon \ZZ \to \ZZ$ which satisfies
\[ f(a) + f(b) + f(c) = \frac{f(a-b) + f(b-c) + f(c-a)}{k} \]
for any integers $a$, $b$, $c$ with $a+b+c=0$.

\section*{Video}
\href{https://www.youtube.com/watch?v=dC9VpiGVRqs}{\texttt{https://youtu.be/dC9VpiGVRqs}}

\section*{External Link}
\url{https://aops.com/community/p26379731}

\newpage

\section*{Solution}
The complete set of solutions is given by
\begin{itemize}
  \ii For $k=1$, $f(x) \equiv C_1 x + C_2(x \mod 2) + C_3$.
  \ii For $k=3$, $f(x) \equiv C_1 x + C_2 x^2$.
  \ii For $k=9$, $f(x) \equiv C_1 x + C_2 x^4$.
  \ii For all other $k$, only $f(x) \equiv C_1 x$.
\end{itemize}
Here $C_1$, $C_2$, $C_3$ are arbitrary integers.
We can check they work, so now we just want to show they are the only ones.

We will solve the functional equation for $f \colon \ZZ \to \CC$,
claiming that the above solution set remains the only one.
If $k=1$, we can shift by constants to get $f(0)=0$;
if $k \neq 1$ apply $a=b=c=0$ to get $f(0) = 0$ anyways.
Now note that $f(x) \equiv x$ is a solution,
so we may shift by the identity to assume $f(-1) = f(1)$.

We will prove in this case, $f \equiv 0$ unless $k=1,3,9$.

Now plug in $(a,b,c) = (n+1,-n,-1)$ and $(a,b,c) = (1,n,-(n+1))$ gives
\begin{align*}
  f(2n+1) + f(-n+1) + f(-n-2)
  &= k \left( f(n+1)+f(-n)+f(-1) \right) \\
  &= k \left( f(-n-1)+f(n)+f(1) \right).
\end{align*}
The last two by induction imply $f$ is even.
Now, by using this and $(a,b,c) = (n,-n,0)$ we obtain
\begin{align*}
  f(2n+1) + f(n+2) + f(n-1) &= k\left( f(n+1) + f(n) + f(1) \right) \\
  f(2n) + 2f(n) &= k\left( 2f(n) + f(0) \right)
  \implies f(2n) = (2k-2)f(n).
\end{align*}
Thus $f$ is determined recursively by $f(1)$ (by induction).
In particular, if $f(1) = 0$ then $f(n) \equiv 0$ by induction.

Now, let us assume $f(1) \neq 0$, and hence by scaling $f(1) = 1$.
We can then compute:
\begin{align*}
  f(1) &= 1 \\
  f(2) &= 2k - 2 \\
  f(3) &= k^2 \\
  f(4) &= 4k^2 - 8k + 4 \\
  f(5) &= k^3 - 2k^2 + 7k - 5 \\
  f(6) &= 2k^3 - 2k^2 \\
  f(7) &= 4k^3 - 6k^2 - 4k + 7 \\
  f(8) &= 8k^3 - 24k^2 + 24k - 8.
\end{align*}
Plug in $(a,b,c)=(5,-3,-2)$ and compute
$f(8) + f(1) + f(7) = k\left( f(5)+f(3)+f(2) \right)$,
which simplifies to give
\[ k^4 - 13k^3 + 39k^2 - 27k = 0 \implies k(k-1)(k-3)(k-9) = 0 \]
so $k=1$, $k=3$, or $k=9$.
In these cases it is easy to check by induction now that
$f(n) = n \mod 2$, $f(n) = n^2$, and $f(n) = n^4$.

\end{document}
