\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USAMO 1997/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 74}
\maketitle
\section*{Problem}
Prove that for any integer $n$,
there exists a unique polynomial $Q$ with coefficients
in $\{0,1,\ldots,9\}$ such that $Q(-2) = Q(-5) = n$.
\section*{Video}
\href{https://www.youtube.com/watch?v=rGoMTlJwq-I&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/rGoMTlJwq-I}}
\newpage
\section*{Solution}
If we let
\[ Q(x) = \sum_{k \ge 0} a_k x^k \]
then $a_k$ is uniquely determined by $n \pmod{2^k}$ and $n \pmod{5^k}$.
Indeed, we can extract the coefficients of $Q$
exactly by the following algorithm:
\begin{itemize}
\ii Define $b_0 = c_0 = n$.
\ii For $i \ge 0$, let $a_i$ be the unique digit
satisfying $a_i \equiv b_i \pmod 2$, $a_i \equiv c_i \pmod 5$.
Then, define
\[ b_{i+1} = \frac{b_i - a_i}{-2}, \qquad
c_{i+1} = \frac{c_i - a_i}{-5}. \]
\end{itemize}
The proof is automatic by Chinese remainder theorem,
so this shows uniqueness already.
The tricky part is to show that all $a_i$ are eventually zero
(i.e.\ the ``existence'' step is nontrivial
because a polynomial may only have finitely many nonzero terms).
In fact, we will prove the following claim:
\begin{claim*}
Suppose $b_0$ and $c_0$ are any integers such that
\[ b_0 \equiv c_0 \pmod 3.\]
Then defining $b_i$ and $c_i$ as above,
we have $b_i \equiv c_i \pmod 3$ for all $i$,
and $b_N = c_N = 0$ for large enough $N$.
\end{claim*}
\begin{proof}
Dropping the subscripts for ease of notation,
we are looking at the map
\[ (b, c) \mapsto \left( \frac{b-a}{-2},
\frac{c-a}{-5} \right) \]
for some $0 \le a \le 9$ (a function in $b$ and $c$).
The $b \equiv c \pmod 3$ is clearly preserved.
Also, examining the size,
\begin{itemize}
\ii If $|c| > 2$,
we have $\left\lvert \frac{c-a}{-5} \right\rvert
\le \frac{|c|+9}{5} < |c|$.
Thus, we eventually reach a pair with $|c| \le 2$.
\ii Similarly, if $|b| > 9$,
we have $\left\lvert \frac{b-a}{-2} \right\rvert
\le \frac{|b|+9}{2} < |b|$,
so we eventually reach a pair with $|b| \le 9$.
\end{itemize}
this leaves us with $5 \cdot 19 = 95$ ordered pairs to check
(though only about one third have $b \equiv c \pmod 3$).
This can be done by the following code:
\begin{lstlisting}[language=Python]
import functools
@functools.lru_cache()
def f(x0, y0):
if x0 == 0 and y0 == 0:
return 0
if x0 % 2 == (y0 % 5) % 2:
d = y0 % 5
else:
d = (y0 % 5) + 5
x1 = (x0 - d) // (-2)
y1 = (y0 - d) // (-5)
return 1 + f(x1, y1)
for x in range(-9, 10):
for y in range(-2, 3):
if (x % 3 == y % 3):
print(f"({x:2d}, {y:2d}) finished in {f(x,y)} moves")
\end{lstlisting}
As this gives the output
\begin{lstlisting}
(-9, 0) finished in 5 moves
(-8, -2) finished in 5 moves
(-8, 1) finished in 5 moves
(-7, -1) finished in 5 moves
(-7, 2) finished in 5 moves
(-6, 0) finished in 3 moves
(-5, -2) finished in 3 moves
(-5, 1) finished in 3 moves
(-4, -1) finished in 3 moves
(-4, 2) finished in 3 moves
(-3, 0) finished in 3 moves
(-2, -2) finished in 3 moves
(-2, 1) finished in 3 moves
(-1, -1) finished in 3 moves
(-1, 2) finished in 3 moves
( 0, 0) finished in 0 moves
( 1, -2) finished in 2 moves
( 1, 1) finished in 1 moves
( 2, -1) finished in 2 moves
( 2, 2) finished in 1 moves
( 3, 0) finished in 2 moves
( 4, -2) finished in 2 moves
( 4, 1) finished in 2 moves
( 5, -1) finished in 2 moves
( 5, 2) finished in 2 moves
( 6, 0) finished in 4 moves
( 7, -2) finished in 4 moves
( 7, 1) finished in 4 moves
( 8, -1) finished in 4 moves
( 8, 2) finished in 4 moves
( 9, 0) finished in 4 moves
\end{lstlisting}
we are done.
\end{proof}
\end{document}