\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2009 C6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 24}
\maketitle
\section*{Problem}
On a $999\times 999$ board a limp rook can move in the following way:
From any square it can move to any of its adjacent squares,
i.e. a square having a common side with it,
and every move must be a turn,
i.e. the directions of any two consecutive moves must be perpendicular.
A non-intersecting route of the limp rook consists
of a sequence of pairwise different squares that the limp rook
can visit in that order by an admissible sequence of moves.
Such a non-intersecting route is called cyclic,
if the limp rook can, after reaching the last square of the route,
move directly to the first square of the route and start over.
How many squares does the longest possible cyclic,
non-intersecting route of a limp rook visit?
\section*{Video}
\href{https://www.youtube.com/watch?v=j6NpL_yF6qI&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/j6NpL\_yF6qI}}
\newpage
\section*{Solution}
The answer is
First consider the following coloring of the board:
\[
\begin{array}{|ccccc}
\hline
A & B & A & B & \dots \\
D & C & D & C & \dots \\
A & B & A & B & \dots \\
D & C & D & C & \dots \\
\vdots & \vdots & \vdots & \vdots & \ddots
\end{array}
\]
A limp rook must move $A \to B \to C \to D \to A \to \dots$
(or backwards, but then just reverse the path)
so an immediate upper bound is given by four times the number of $C$'s,
which is equal to $4 \cdot 499^2$.
We will improve this bound slightly.
\begin{claim*}
The path of the limp rook cannot move between
non-orthogonally adjacent letter $C$'s.
\end{claim*}
\begin{proof}
Assume not.
Since $C$ appears every four moves, the limp
rook must have reached a diagonally adjacent $C$.
We illustrate the situation below,
with cells denoted by points rather than squares.
Consider the $C$ which is wrapped around by the path
(see illustration).
The path reaches this $C$ eventually to,
and most do so via $B \to C \to D$ as shown.
\begin{center}
\begin{asy}
size(9cm);
draw( (0,2)--(1,2), red, EndArrow, Margins);
draw( (1,2)--(1,1), red, EndArrow, Margins);
draw( (1,1)--(2,1), red, EndArrow, Margins);
draw( (2,1)--(2,0), red, EndArrow, Margins);
draw( (2,3)--(2,2), deepcyan, EndArrow, Margins);
draw( (2,2)--(3,2), deepcyan, EndArrow, Margins);
draw( (3,2)..(1.5,-1)..(0,2), grey+dashed, EndArrow, Margins);
draw( (2,0)..(4,1.5)..(2,3), grey+dashed, EndArrow, Margins);
dot("$C$", (0,2), dir(45), red);
dot("$D$", (1,2), dir(45), red);
dot("$A$", (1,1), dir(45), red);
dot("$B$", (2,1), dir(45), red);
dot("$C$", (2,0), dir(45), red);
dot("$B$", (0,1), dir(45));
dot("$C$", (0,0), dir(45));
dot("$D$", (1,0), dir(45));
dot("$B$", (2,3), dir(135), deepcyan);
dot("$C$", (2,2), dir(225), deepcyan);
dot("$D$", (3,2), dir(90), deepcyan);
\end{asy}
\end{center}
However, we now see there is no non-intersecting way
that we could unite these two paths (grey paths must intersection),
which gives a contradiction.
\end{proof}
Because of this, the number of $C$'s used must be even,
so we have a bound of $4 \cdot (499^2-1)$ now.
The construction is achieved by a ``spiral path'' we illustrate below,
here for a $15 \times 15$ grid but which can be generalized readily.
\begin{center}
\begin{asy}
size(14cm);
pair P = (0,12); // current pointer
for (int i=-1; i<14; ++i) {
for (int j=-1; j<14; ++j) {
dot((i,j), rgb(0.8,0.8,0.8));
}
}
pen rook = red;
path wiggle = (0,0)--(1,0)--(1,1)--(2,1)--(2,0);
path squiggle = (0,0)--(0,1)--(1,1)--(1,0)--(2,0);
for (int i=0; i<6; ++i) {
draw(shift(P) * wiggle, rook);
P += (2,0);
}
for (int i=0; i<6; ++i) {
draw(shift(P) * rotate(-90) * squiggle, rook);
P += (0, -2);
}
for (int i=0; i<6; ++i) {
draw(shift(P) * rotate(180) * wiggle, rook);
P += (-2, 0);
}
draw(shift(P) * rotate(90) * squiggle, rook);
P += (0,2);
for (int i=0; i<5; ++i) {
draw(shift(P) * yscale(-1) * wiggle, rook);
P += (2, 0);
}
for (int i=0; i<4; ++i) {
draw(shift(P) * yscale(-1) * rotate(-90) * squiggle, rook);
P += (0, 2);
}
for (int i=0; i<4; ++i) {
draw(shift(P) * xscale(-1) * wiggle, rook);
P += (-2, 0);
}
for (int i=0; i<2; ++i) {
draw(shift(P) * xscale(-1) * rotate(-90) * squiggle, rook);
P += (0, -2);
}
for (int i=0; i<2; ++i) {
draw(shift(P) * yscale(-1) * wiggle, rook);
P += (2, 0);
}
draw(shift(P) * yscale(-1) * rotate(-90) * squiggle, rook);
P += (0,2);
draw(shift(P) * wiggle, rook);
P += (2,0);
for (int i=0; i<2; ++i) {
draw(shift(P) * rotate(-90) * squiggle, rook);
P += (0, -2);
}
for (int i=0; i<4; ++i) {
draw(shift(P) * rotate(180) * wiggle, rook);
P += (-2, 0);
}
for (int i=0; i<4; ++i) {
draw(shift(P) * rotate(90) * squiggle, red);
P += (0, 2);
}
for (int i=0; i<7; ++i) {
for (int j=0; j<7; ++j) {
dot("$C$", (2*i,2*j), dir(45), blue);
}
}
\end{asy}
\end{center}
\end{document}