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

\begin{document}
\title{China 2021/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 123}
\maketitle

\section*{Problem}
Solve over positive integers the functional equation
\[ f(f(x)+y) \mid x+f(y). \]

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

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

\newpage

\section*{Solution}
There are three families of solutions:
\begin{itemize}
  \ii $f$ is the identity function;
  \ii $f(n) = 1$ for $n \ge 2$, where $f(1)$ is any positive integer.
  \ii $f(n) = 2$ for $n$ even, $f(n) = 1$ for odd $n \ge 3$,
  and $f(1)$ is any odd positive integer.
\end{itemize}
The verification is easy, so we prove these are the only solution.
The proof is split into two main cases.

\paragraph{Case where $f$ is not injective.}
Let \[ T = \min_{f(a)=f(b), a<b} (b-a). \]
Then all outputs of $f$ are eventually divisors of $T$, as
\[ f(y+f(a)) = f(y+f(b)) \mid \gcd(f(y)+a,f(y)+b) \mid b-a \qquad \forall y > 0. \]
\begin{claim*}
  We have $T \le 2$.
\end{claim*}
\begin{proof}
  If $T > 2$, then look any $T$ consecutive outputs.
  They were supposed to be distinct divisors of $T$,
  impossible for $T > 2$.
\end{proof}

If $T=1$, then for any $n \ge 2$, let $y=n-1$ and let $x$ be a large integer.
Then we have $f(n) \mid x + f(n-1)$ for all large $x$, forcing $f(n)+1$.

If $T=2$, then it follows $f$ must alternate between $1$ and $2$ eventually.
Again, $f(n) \le 2$ follows for $n \ge 2$ as in the previous case,
by letting $y=n-1$ and $x$ be large with $f(x)=1$.
We can then quickly verify that only the situation where
$f(\text{even})=\text{even}$ bears solutions, the ones we claimed earlier.

\paragraph{Case where $f$ is not injective.}
Let $c = f(1)$.
Taking $x=1$ then gives
\[ f(y+c) \le f(y)+1. \]
This implies
\[ f(n) \leq \frac 1c n + \max \left\{ f(1), \dots, f(c) \right\}. \]
For $f$ to be injective, we must then have $c=1$.
Finally, $f(y+1) \le f(y)+1$ together with $f$ injective
then forces $f$ to be the identity function, by induction.

\end{document}
