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

\begin{document}
\title{USAMTS 4/2/34}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 111}
\maketitle

\section*{Problem}
Fix an integer $k \ge 2$.
Find the smallest positive integer $c_k$ such that
a toroidal $k \times k$ board can be colored with one of $c_k$ colors,
where orthogonal and diagonal neighbors of a point are different colors.

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

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

\newpage

\section*{Solution}
The answer is
\[
  c_k =
  \begin{cases}
    9 & \text{if $k=3$} \\
    4 & \text{if $k$ is even} \\
    5 & \text{if $k \ge 5$ is odd}.
  \end{cases}
\]
When $k=3$, nine colors are both necessary and sufficient
because the graph we are trying to color is $K_9$
(every two cells are the same color).

When $k$ is even, a coloring using $(x \bmod 2, y \bmod 2)$ works.
It's also best possible because every cell of each $2 \times 2$
must be a different color.

The main interesting is $k \ge 5$ odd.
\begin{claim*}
  At least five colors are necessary when $k$ is odd.
\end{claim*}
\begin{proof}
  In fact one cannot even color a $2 \times k$ toroidal grid
  with four colors,
  since if the first column is say red/pink
  and the second column is blue/purple
  then the columns will alternate red/pink and blue/purple.
\end{proof}

On the other hand, a construction
for $k=13$ that generalizes easily is shown below.
\begin{center}
\begin{asy}
  unitsize(0.7cm);
  string[] coloring = {
    "RGYKBRGRGRGRG",
    "YKBRGYKYKYKYK",
    "BRGYKBRBRBRBR",
    "GYKBRGYGYGYGY",
    "KBRGYKBKBKBKB",
    "RGYKBRGRGRGRG",
    "YKBRGYBYBYBYB",
    "RGYKBRGRGRGRG",
    "YKBRGYBYBYBYB",
    "RGYKBRGRGRGRG",
    "YKBRGYBYBYBYB",
    "RGYKBRGRGRGRG",
    "YKBRGYBYBYBYB",
  };
  string s;
  for (int x=0; x<13; ++x) {
    for (int y=0; y<13; ++y) {
      s = substr(coloring[12-y], x, 1);
      if (s=="R") { fill(shift(x,y)*unitsquare, lightred); }
      if (s=="Y") { fill(shift(x,y)*unitsquare, paleyellow); }
      if (s=="B") { fill(shift(x,y)*unitsquare, lightcyan); }
      if (s=="G") { fill(shift(x,y)*unitsquare, lightgreen); }
      if (s=="K") { fill(shift(x,y)*unitsquare, lightgray); }
      label("$"+s+"$", (x+0.5, y+0.5));
    }
  }
  draw(box((0,0), (13,13)),  black+4.5);
  draw((0,8)--(13,8), black+4.5);
  draw((5,0)--(5,13), black+4.5);
\end{asy}
\end{center}

\end{document}
