\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 1990/17}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 47}
\maketitle
\section*{Problem}
Unit cubes are made into beads by drilling a hole
through them along a diagonal.
The beads are put on a string in such a way
that they can move freely in space under the restriction
that the vertices of two neighboring cubes are touching.
Let $A$ be the beginning vertex and $B$ be the end vertex.
Let there be $pqr$ cubes on the string.
\begin{enumerate}
\ii[(a)] Determine for which values of $p,q,r \ge 1$,
it is possible to build a block with dimensions $p \times q \times r$.
\ii[(b)] The same question as (a) with
the extra condition that $A=B$.
\end{enumerate}
\section*{Video}
\href{https://www.youtube.com/watch?v=UWBYzWeJwYc&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/UWBYzWeJwYc}}
\section*{External Link}
\url{https://aops.com/community/p1225240}
\newpage
\section*{Solution}
For (a), the answer is always yes;
whereas for (b), the answer is only if at least two
of $p$, $q$, $r$ are even.
Let the box $\mathcal B$
be located in space spanning $(0,0,0)$ to $(p,q,r)$.
Then the string can move from $(x,y,z)$
to $(x \pm 1, y \pm 1, z \pm 1)$.
So, the string is going to visit only points of two parity
classes in $\FF_2 \times \FF_2 \times \FF_2$, say
$(\eps_x \bmod 2, \eps_y \bmod 2, \eps_z \bmod 2)$
and $(1+\eps_x \bmod 2, 1+\eps_y \bmod 2, 1+\eps_z \bmod 2)$.
However, every unit cube has a string through it, so we find that the
string visits every point of this form in $\mathcal B$.
Let us denote the set of points by $V$
(which depends on the choice of $(\eps_x, \eps_y, \eps_z)$).
Hence the question is asking when we can have a Eulerian
path or circuit on the resulting graph $G$
(whose vertex set is $V$ and whose edges are the string).
However, the degrees of vertices of $G$ are always even \emph{except}
for the corners of $\mathcal B$, i.e.\ the eight points
\[
\Big\{ (0,0,0), \; (p,0,0), \; (0,q,0), \; (0,0,r), \;
(p,q,0), \; (p,0,r), \; (0,q,r), \; (p,q,r) \Big\}.
\]
\begin{itemize}
\ii We can always ensure there are at most
two corners in $V$
by choosing $\eps_x$, $\eps_y$, $\eps_z$ randomly;
the expected number of corners is $\frac14 \cdot 8 = 2$.
\ii We can ensure there are zero corners
if at least two of $(p,q,r)$ are even;
otherwise we cannot.
\end{itemize}
Hence by the classical theorem on Eulerian paths and circuits,
(a) is possible always,
(b) is possible when at least two of $(p,q,r)$ are even.
\end{document}