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

\begin{document}
\title{ToT Fall 1999 J-A6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 32}
\maketitle

\section*{Problem}
A rook is allowed to move one cell either horizontally or vertically.
After $64$ moves the rook visited all cells of the $8 \times 8$ chessboard
and returned back to the initial cell.
Prove that the number of moves in the vertical direction
and the number of moves in the horizontal direction cannot be equal.

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

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

\newpage

\section*{Solution}
Identify the cells of the board as points of an equally spaced grid.
We view the path of the rook as a closed cycle $\mathcal P$
which is naturally a (simple) polygon (but necessarily non-convex)
whose interior angles are either $90^{\circ}$ or $270^{\circ}$.
By the Jordan curve theorem, the polygon has an interior.

We will perform operations which
\begin{itemize}
  \ii gradually increase the area of $\mathcal P$,
  \ii while maintaining the property that
  all $64$ points either remain on $\mathcal P$ or inside it.
\end{itemize}
The main idea is the following foothold.

\begin{claim*}
  If the properties above hold then
  either $\mathcal P$ is a rectangle
  or there exists two consecutive $270^{\circ}$
  angles of $\mathcal P$ which are one unit apart (a ``U-shape'').
\end{claim*}
\begin{proof}
  Suppose that $\mathcal P$ has no U-shapes.
  We exhibit an injective map from every $270\dg$ angle
  of $\mathcal P$ to some $90\dg$ angle of $\mathcal P$.

  Take any $270^{\circ}$ angle with vertex at $X$, as shown below,
  and look at the point $Y$ marked in red in the figure below
  (assume without loss of generality the orientation shown).
  Because there are no U-turns, we are assuming $Y$ is
  But we are assuming no lattice points are outside $\mathcal P$,
  so $Y$ is part of $\mathcal P$ later;
  but then it is also is part of an angle of $\mathcal P$.
  \begin{center}
  \begin{asy}
    size(4cm);
    pair A = (0,1);
    pair B = (0,0);
    pair C = (1,0);
    fill((-0.8,0.5)..(-0.4,1.4)..(0,1.7)--A--B--C--(1.7,0)..(1.4,-0.4)..(0.5,-0.8)
      --(-0.8,-0.8)--cycle, palecyan);
    dotfactor *= 2;
    dot(A, blue);
    dot("$X$", B, dir(45), blue);
    dot(C, blue);
    draw((-0.8,0.5)..(-0.4,1.4)..(0,1.7)--A--B--C--(1.7,0)..(1.4,-0.4)..(0.5,-0.8), blue);
    pair Y = (1,1);
    fill( (2,1)--Y--(1,2)--(2,2)--cycle, palered );
    draw( (2,1)--Y--(1,2), red );
    dot("$Y$", Y, dir(225), red);
  \end{asy}
  \end{center}
  Since $\mathcal P$ has a well-defined interior and exterior,
  and the interior is to the southwest of $X$,
  it follows the interior of $\mathcal P$ is to the northeast of $Y$.
  So we take the map $X \mapsto Y$.
  It is obviously injective and this completes the proof.

  Since the total sum of angle measures is $180^{\circ} \cdot (n-2)$
  where $n$ is the number of sides of $\mathcal P$,
  this will imply $n \le 4$, i.e.\ that $n$ is a rectangle.
  In other words, the only polygons that have no U-shape are rectangles.
\end{proof}

Given a U-shape as described, we apply an operation
to add the ``missing'' square into $\mathcal P$ as shown below.
Doing this preserves all the condition and leaves a ``green domino''
(two adjacent cells); so we apply the operation until we get a rectangle.
\begin{center}
\begin{asy}
  size(9cm);
  picture before;
  picture after;
  dotfactor *= 2;
  filldraw(before, (-1,2)--(0,2)--(0,0)--(1,0)--(1,2)--(2,2)--(2,-1)--(-1,-1)--cycle,
    palecyan, blue);
  dot(before, (1,0), blue);
  dot(before, (0,0), blue);
  dot(before, (0,1), blue);
  dot(before, (1,1), blue);

  filldraw(after, (-1,2)--(0,2)--(0,1)--(1,1)--(1,2)--(2,2)--(2,-1)--(-1,-1)--cycle,
    palecyan, blue);
  dot(after, (1,0), deepgreen);
  dot(after, (0,0), deepgreen);
  dot(after, (0,1), blue);
  dot(after, (1,1), blue);
  draw(after, (0,0)--(1,0), deepgreen);
  draw(after, box((-0.4,-0.4),(1.4,0.4)), deepgreen);

  add(shift(-5,0)*before);
  add(after);
  label(scale(4)*"$\Rightarrow$", (-2,0.3), red);
\end{asy}
\end{center}

Since no points lie outside the rectangle,
the final rectangle must be the outer perimeter of the grid;
in other words, the final configuration gives a green domino tiling
of the interior $6 \times 6$ lattice, as shown.
\begin{center}
\begin{asy}
  size(7cm);
  filldraw(box( (0,0), (7,7) ), palecyan, blue);
  for (int i=0; i<=6; ++i) {
    dot((0,i), blue);
    dot((i+1,0), blue);
    dot((6-i,7), blue);
    dot((7,7-i), blue);
  }
  dotfactor *= 2;
  picture domino;
  dot(domino, (0,0), deepgreen);
  dot(domino, (1,0), deepgreen);
  draw(domino, (0,0)--(1,0), deepgreen);
  draw(domino, box((-0.4,-0.4),(1.4,0.4)), deepgreen);
  add(shift(1,1)*domino);
  add(shift(1,2)*rotate(90)*domino);
  add(shift(2,2)*rotate(90)*domino);
  add(shift(1,4)*rotate(90)*domino);
  add(shift(2,4)*domino);
  add(shift(1,6)*domino);
  add(shift(2,5)*domino);
  add(shift(3,6)*domino);
  add(shift(4,4)*rotate(90)*domino);
  add(shift(5,5)*rotate(90)*domino);
  add(shift(6,5)*rotate(90)*domino);
  add(shift(5,3)*domino);
  add(shift(5,4)*domino);
  add(shift(6,1)*rotate(90)*domino);
  add(shift(4,1)*domino);
  add(shift(4,2)*domino);
  add(shift(3,3)*domino);
  add(shift(3,1)*rotate(90)*domino);
\end{asy}
\end{center}
Since the orientation of the dominoes is opposite the orientation of the
two ``deleted'' segments when it was created,
the problem is reduced to proving the following claim.
\begin{claim*}
  A domino tiling of a $6 \times 6$ board
  has an unequal number of horizontal and vertical dominoes.
\end{claim*}
\begin{proof}
  There are $18$ dominoes and we claim there are an even number of each orientation.
  Indeed, color the odd-numbered rows; there are $18$ shaded cells now.
  A vertical domino covers an odd number of shaded cells,
  while a horizontal domino covers an even number of shaded cells.
  So there are an even number of vertical dominoes, as needed.
\end{proof}

\begin{remark*}
Here is a counterexample for an $10 \times 10$ board which generalizes
easily, so the problem is false in general if $8$ is replaced by a
$2 \bmod 4$ number.
\begin{center}
\begin{asy}
  size(2cm);
  path p = (0,0)--(4,0)--(4,1)--(0,1)--(0,2)--(4,2)--(4,3)--(0,3)--(0,4)--(4,4);
  draw( (4,-5)--(5,-5), grey );
  draw( (0,-1)--(0,1), grey );
  draw( (9,-1)--(9,1), grey );
  draw( (4,4)--(5,4), grey );
  draw(p, red+1);
  draw(shift(4,-5)*rotate(90)*p, blue+1);
  draw(shift(9,-1)*rotate(180)*p, orange+1);
  draw(shift(5,4)*rotate(270)*p, deepgreen+1);
\end{asy}
\end{center}
\end{remark*}

\end{document}
