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

\begin{document}
\title{Shortlist 2020 N5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 83}
\maketitle

\section*{Problem}
Determine all functions $f \colon \ZZ_{>0} \to \ZZ_{\ge 0}$
satisfying the two conditions:
\begin{itemize}
  \item $f(x y)=f(x)+f(y)$ for every positive integer $x$ and $y$;
  \item there are infinitely many positive integers $n$
    such that $f(k)=f(n-k)$ for all $k<n$.
\end{itemize}

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

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

\newpage

\section*{Solution}
\emph{The following solution was given by Ankan Bhattacharya.}

The answer is and $f(x) \equiv c \nu_p(x)$
for any prime $p$ and constant $c \ge 0$.
These obviously work.

For the other direction,
let $\mathcal M$ be the set of integers satisfying the second condition.
\begin{claim*}
  $\mathcal M$ is closed under division.
\end{claim*}
\begin{proof}
  Tautological.
\end{proof}

Now assuming $f$ is not identically zero,
fix $p$ the smallest prime for which $f(p) > 0$.
\begin{claim*}
  This prime $p$ divides any element of $\mathcal M$
  which is greater than $p$.
\end{claim*}
\begin{proof}
  Suppose $m \in \mathcal M$ and $m > p$.
  Use division algorithm to get $m = p \cdot s + r$ where $0 \le r < p$.
  If $r > 0$, then
  \[ f(r) = f(p \cdot s) = f(p) + f(s) > 0 \]
  a contradiction to minimality of $p$.
\end{proof}

\begin{claim*}
  Every element of $\mathcal M$ equals a power of $p$
  times an integer less than or equal to $p$.
\end{claim*}
\begin{proof}
  Follows from the last two claims.
\end{proof}

Assume for contradiction
$q$ is a prime greater than $p$ and with $f(q) > 0$.
For some $p^e \in \mathcal M$ exceeding $q$, use the division algorithm to get
\[ p^e - qs = r < q \]
and hence
\[ f(q) + f(s) = f(r), \qquad r < q. \]
But evidently $\nu_p(s) = \nu_p(r)$ and $\nu_q(r) = 0$,
hence $f(s) = f(r)$, contradiction.

\end{document}
