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

\begin{document}
\title{ELMO 2013/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 51}
\maketitle

\section*{Problem}
A function $f \colon \ZZ \to \ZZ$ is given.
Suppose that for every integer $n \ge 0$,
there are at most $0.001n^2$ pairs of integers $(x,y)$
for which $f(x+y) \neq f(x)+f(y)$ and $\max\{ \lvert x \rvert, \lvert y \rvert \} \le n$.
Is it possible that for some integer $n \ge 0$, there are more than $n$ integers $a$
such that $f(a) \neq a \cdot f(1)$ and $\lvert a \rvert \le n$?

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

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

\newpage

\section*{Solution}
The answer is no.

Let's say an integer is \emph{bad} if $f(n) \neq n \cdot f(1)$.
It is not hard to see that any bad integer
must have absolute value at least $30$.

Let's say a pair of integers is \emph{bad} if $f(x+y) \neq f(x)+f(y)$.

\begin{claim*}
  Let $n \ge 1$, and suppose there
  are $\eps n$ bad integers in $[-n,n]$.
  Then
  \[ \eps \left( 1 - 2 \eps \right) < 0.001. \]
\end{claim*}
\begin{proof}
  If $\eps = 0$ there is nothing to prove.

  Otherwise, pick a bad integer $b$ and consider
  \[ \ell_b = \left\{ (x,y) \mid x,y \in [-n,n], x+y=b \right\}. \]
  (We call this a ``line'' colloquially, thinking of it in the $xy$-plane.)
  Note that:
  \begin{itemize}
    \ii There are at least $n$ points on $\ell_b$.
    \ii For every $(x,y) \in \ell_b$, either the pair itself is bad,
    or one of $x$ or $y$ is bad.
    (Otherwise, putting $(x,y)$ in the functional equation
    would contradict badness of $b$).
    \ii Therefore, there are at least $n - 2\eps n$ bad pairs on $\ell_b$.
  \end{itemize}
  Taking the union across all $\eps n$ lines $\ell_b$,
  we conclude the total number of bad pairs is at least
  \[ \eps n \cdot (1 - 2 \eps) n. \]
  This gives the desired result.
\end{proof}
Note that the solution to the above quadratic is $\eps < 0.001002$ and $\eps > 0.498998$
(decimal approximations for convenience).

Viewing $\eps$ as a function $\eps(n)$ now,
we not that $\eps(n) = 0$ initially for $n = 1, 2, \dots, 30$.
There is no way for $\eps(n)$ to ``jump''
in the sense that $\eps(n) < 0.1$ and $\eps(n+1) > 0.4$, so this ends the proof.

\end{document}
