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

\begin{document}
\title{Iberoamerican 2019/5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 109}
\maketitle

\section*{Problem}
Don Miguel places a token in one of the $(n+1)^2$ vertices determined
by an $n \times n$ board.
A move consists of moving the token from the vertex on which
it is placed to an adjacent vertex which is at most $\sqrt2$ away,
as long as it stays on the board.
A path is a sequence of moves such that the token was
in each one of the $(n+1)^2$ vertices exactly once.
What is the maximum number of diagonal moves (those of length $\sqrt2$)
that a path can have in total?

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

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

\newpage

\section*{Solution}
When $n$ is odd, the answer is $n^2+n$,
while when $n$ is even, the answer is $n^2$.
Constructions are shown below for $n=9$ and $n=8$ which obviously generalize.

\begin{center}
\begin{asy}
  size(12cm);
  path green_zigzag =
  (0,1)--(1,0)--(2,1)--(3,0)--(4,1)--(5,0)--(6,1)--(7,0)--(8,1)--(9,0);
  path blue_zigzag =
  (0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0)--(7,1)--(8,0)--(9,1);
  for (int t=0; t<=9; ++t) {
    draw((0,t)--(9,t), lightgrey);
    draw((t,0)--(t,9), lightgrey);
  }
  draw(box( (0,0),(9,9)),  grey );
  for (int i=0; i<5; ++i) {
    draw(shift(0,2*i)*green_zigzag, deepgreen);
    draw(shift(0,2*i)*blue_zigzag, blue);
    draw( (9,2*i)--(9,2*i+1), red+1.5 );
    if (i != 4) {
      draw( (0,2*i+1)--(0,2*i+2), red+1.5 );
    }
  }
  for (int x=0; x<=9; ++x) {
     for (int y=0; y<=9; ++y) {
       if ((x+y)#2 == (x+y)/2) {
         dot( (x,y), blue );
       }
     }
   }

  for (int t=0; t<=8; ++t) {
    draw((10,t)--(18,t), lightgrey);
    draw((t+10,0)--(t+10,8), lightgrey);
  }
  draw(box( (10,0),(18,8)), grey);
  for (int i=0; i<=4; ++i) {
    draw((10+2*i,0)--(10,2*i), blue);
    draw((10+2*i,8)--(18,2*i), blue);
  }
  for (int i=0; i<4; ++i) {
    draw((10+2*i+1,0)--(10,2*i+1), deepgreen);
    draw((10+2*i+1,8)--(18,2*i+1), deepgreen);
    draw((2*i+10,0)--(2*i+10+1,0), red+1.5);
    draw((2*i+10+1,8)--(2*i+10+2,8), red+1.5);
    draw((10,2*i+1)--(10,2*i+2), red+1.5);
    draw((18,2*i)--(18,2*i+1), red+1.5);
  }
  for (int x=0; x<=8; ++x) {
     for (int y=0; y<=8; ++y) {
       if ((x+y)#2 == (x+y)/2) {
         dot( (x+10,y), blue);
       }
     }
   }

   label("$n=9$", (4.5,0), dir(-90));
   label("$n=8$", (14,0), dir(-90));
\end{asy}
\end{center}

To show the bound, impose coordinates $(x,y)$ with $0 \le x \le n$
and $0 \le y \le n$, and color blue any point with $x+y \equiv 0 \pmod 2$
(as shown in the examples above); else color it green (not drawn).
Imagine taking our given path and deleting every
orthogonal move of distance $1$ (i.e.\ not $\sqrt2$).
Doing this deletion gives us a bunch of \emph{zigzags} ---
graph-theoretic paths of length $1$ or more
where every two adjacent vertices are $\sqrt 2$ apart.
The zigzags will alternate between passing through blue dots
(we call these \emph{blue zigzags})
and through green dots (we call these \emph{green zigzags}).

\paragraph{Case where $n$ is even.}
We give an estimate on the number of blue zigzags.
\begin{claim*}
  If $n$ is even, there are at least $n+1$ blue zigzags.
\end{claim*}
\begin{proof}
  There are $\left( \half n + 1 \right)^2$ blue dots
  in odd-numbered rows,
  and $\left( \half n \right)^2$ blue dots in even-numbered rows.
  The difference between this is $n+1$.
  Since blue zigzags must alternate between odd-numbered rows
  and even-numbered rows, there must be at least $n+1$.
\end{proof}
Since we know there are at least $n+1$ blue zigzags,
there must have been at least $n$ green zigzags,
so there were a total of at least $2n+1$ zigzags.
In other words, there were at least $2n$ orthogonal moves
in the original given path.
So the number of diagonal steps is at most $((n+1)^2-1)-2n = n^2$.

\paragraph{Case where $n$ is odd.}
The blue and green zigzags play the same role, so we bound both:
\begin{claim*}
  [USAMO 2008/3]
  If $n$ is odd, there are at least $\frac{n+1}{2}$
  blue zigzags, and at least $\frac{n+1}{2}$ green zigzags.
\end{claim*}
\begin{proof}
  This is USAMO 2008 problem 3 rotated by $90\dg$.
\end{proof}
Hence there were a total of at least $n+1$ zigzags.
In other words, there were at least $n$ orthogonal moves
in the original given path.
So the number of diagonal steps is at most $((n+1)^2-1)-(n+1) = n^2+n$.

\end{document}
