\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Schweitzer 2020/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 99}
\maketitle
\section*{Problem}
We say that two sequences of positive integers
$(x_n)_{n \ge 1}$ and $(y_n)_{n \ge 1}$ are completely different
if $x_n \neq y_n$ for all $n\in \mathbb{N}$.
Let $F$ be a function assigning a positive integer
to every sequence of positive integers such that
$F(x) \neq F(y)$ for any pair of completely different sequences $x$, $y$,
and for constant sequences we have $F \left((k,k,\dots)\right)=k$.
Prove that there exists $n$ such that $F(x)=x_{n}$
for all sequences $x$.
\section*{Video}
\href{https://www.youtube.com/watch?v=i1d3h_Rs9Iw&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ&index=5&t=1818s}{\texttt{https://youtu.be/i1d3h\_Rs9Iw}}
\newpage
\section*{Solution}
By permuting indices suitably,
we are going to assume $F(1,2,3,\dots) = 1$
and show that $F$ returns the first value.
\begin{claim*}
$F(x_\bullet)$ always returns an element
that appears in $x_\bullet$.
\end{claim*}
\begin{proof}
If $F(x_\bullet) = k$ and $k \notin x_\bullet$,
then $x_\bullet$ is completely different
from $(k,k,\dots)$, yet $F(k,k,\dots) = k$.
\end{proof}
\begin{claim*}
If $x_\bullet$ is a sequence that contains
only two different numbers, then $F(x_\bullet) = x_1$.
\end{claim*}
\begin{proof}
Call the two numbers $x_1 = a$ and $b$.
First, we resolve the case where $a,b \ge 2$.
Indeed, note that
\[ F(b,1,1,1,\dots) = b \]
since that sequence is completely different from $(1,2,3,\dots)$
so its $F$-value cannot be $1$, hence must be $b$.
But $(b,1,1,\dots)$ is completely different from $(x_\bullet)$
so we get $F(x_\bullet) = a$ as desired.
To deal with the case $a=1$,
we pick any third number $c$ not equal to $1$ or $b$,
and consider the sequence
\[
y_n = \begin{cases}
b & x_n = 1 \\
c & x_n = b.
\end{cases}
\]
Now $F(y_n) = b$, and $y_n$ is completely different from $x_n$.
So this forces $F(x_n) = a$.
Similarly, to deal with the case $b=1$,
we pick any third number $c$ not equal to $a$ or $1$,
and consider the sequence
\[
y_n = \begin{cases}
b & x_n = a \\
c & x_n = 1.
\end{cases}
\]
Now $F(y_n) = b$, and $y_n$ is completely different from $x_n$.
So this forces $F(x_n) = a$ too.
\end{proof}
We now finish the general case.
Suppose for contradiction that
\[ F(a_1, a_2, \dots) = r \neq a_1. \]
Then we can construct a sequence $b_n$ by
\[
b_n = \begin{cases}
r & a_n = a_1 \\
a_1 & \text{otherwise}
\end{cases}
\]
By construction, $a_n$ is completely different from $b_n$.
But the previous claim gives $F(b_n) = r$, contradiction.
\end{document}