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

\begin{document}
\title{EGMO 2024/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 146}
\maketitle

\section*{Problem}
Two different integers $u$ and $v$ are written on a board.
We perform a sequence of steps. At each step we do one of the following two operations:
\begin{enumerate}[(i)]
  \ii If $a$ and $b$ are different integers on the board,
  then we can write $a + b$ on the board, if it is not already there.
  \ii If $a$, $b$ and $c$ are three different integers on the board,
  and if an integer $x$ satisfies $ax^2 +bx+c = 0$,
  then we can write $x$ on the board, if it is not already there.
\end{enumerate}
Determine all pairs of starting numbers $(u, v)$
from which any integer can eventually be written on the board
after a finite sequence of steps.

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

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

\newpage

\section*{Solution}
Note that the following cases are impossible:
\begin{itemize}
  \ii If either $u = 0$ or $v = 0$, operation (i) cannot produce numbers,
  and (ii) cannot be used at all.
  Hence the task is obviously impossible.

  \ii If $\{u,v\} = \{-1,1\}$, operation (i) produces $0$,
  and no more numbers can be added with operation (i) or (ii).
  So this case cannot be done.

  \ii If $u,v < 0$, then we claim all numbers written are negative.
  Indeed, (i) respects this;
  and also, if $a,b,c < 0$ then no $x > 0$ can obey $ax^2+bx+c=0$.
  So the task is impossible here too.
\end{itemize}
We claim the task is possible in all other cases.
\begin{claim*}
  We can write $-1$.
\end{claim*}
\begin{proof}
  We can write $u+v$, and the three numbers $u$, $v$, $u+v$ are different.
  The quadratic $ux^2 + (u+v)x + v$ has root $-1$.
\end{proof}
\begin{claim*}
  We can write a positive number $m \ge 2$ on the board.
\end{claim*}
\begin{proof}
  We assumed that at least one of $u$ and $v$; say $u = \max(u,v) > 0$.
  If $u \ge 2$ we're done.
  Suppose $u = 1$; then $v$ is some negative number with $v \le -2$.
  We can write $(-1) + 1 = 0$.
  Then $0x^2 + x + v = 0$ has root $-v$, which is the desired number.
\end{proof}
Let $m \ge 2$ be from the claim; then we can write $m-1 \ge 1$,
and hence we can write all of $m-1$, $2m-1$, $3m-1$, \dots.
Thus (because we have $-1$) we can then write any nonnegative integer
by adding $-1$ several times.
(However, we cannot write $-2$ in this way, because we cannot add $-1$ to itself.)

But now for $n > 0$, $-n$ is a root of $0x^2 + x + n$,
so we can write the negative integers too.

\end{document}
