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

\begin{document}
\title{USAMO 2021/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 65}
\maketitle

\section*{Problem}
The Planar National Park is a undirected 3-regular planar graph
(i.e.\ all vertices have degree $3$).
A visitor walks through the park as follows:
she begins at a vertex and starts walking along an edge.
When she reaches the other endpoint, she turns left.
On the next vertex she turns right, and so on,
alternating left and right turns at each vertex.
She does this until she gets back to the vertex where she started.
What is the largest possible number of times she could have entered
any vertex during her walk, over all possible layouts of the park?

\section*{Video}
\href{https://www.youtube.com/watch?v=9WNgDETHOlI&t=1325}{\texttt{https://youtu.be/9WNgDETHOlI}}

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

\newpage

\section*{Solution}
The answer is $3$.

We consider the trajectory of the visitor as an ordered sequence of \emph{turns}.
A turn is defined by specifying a vertex, the incoming edge, and the outgoing edge.
Hence there are six possible turns for each vertex.

\begin{claim*}
  Given one turn in the sequence, one can reconstruct the entire sequence of turns.
\end{claim*}
\begin{proof}
  This is clear from the process's definition: given a turn $t$,
  one can compute the turn after it and the turn before it.
\end{proof}

This implies already that the trajectory of the visitor,
when extended to an infinite sequence, is totally periodic (not just eventually periodic),
because there are finitely many possible turns, so some turn must be repeated.
So, any turn appears at most once in the period of the sequence,
giving a na\"{\i}ve bound of $6$ for the original problem.

However, the following claim improves the bound to $3$.
\begin{claim*}
  It is impossible for both of the turns $a \to b \to c$ and $c \to b \to a$ to occur
  in the same trajectory.
\end{claim*}
\begin{proof}
  If so, then extending the path, we get $a \to b \to c \to d \to e \to \dotsb$
  and $\dots \to e \to d \to c \to b \to a$, as illustrated below in red and blue respectively.
  \begin{center}
  \begin{asy}
    defaultpen(fontsize(11pt));
    dotfactor *= 1.8;
    pair A = (0,0);
    pair B = (1,1);
    pair C = (0,2);
    pair D = (1,3);
    pair E = (0,4);
    draw(A--B--C--D--E--(0.5,4.5), black+1.3);
    draw( (0.5,4.5)--(0.8,4.8), black+1.3+dotted );
    draw((1,-1)--A--(-1,0), grey);
    draw(B--(2,1), grey);
    draw(C--(-1,2), grey);
    draw(D--(2,3), grey);
    draw(E--(-1,4), grey);
    dot("$a$", A, -dir(B-A), deepgreen);
    dot("$b$", B, -dir(C-B), deepgreen);
    dot("$c$", C, -dir(D-C), deepgreen);
    dot("$d$", D, -dir(E-D), deepgreen);
    dot("$e$", E, dir(90), deepgreen);
    draw( (1,0.2)..(1.4,1)..(1,1.8), red+1.8, EndArrow(TeXHead));
    draw( (1,2.2)..(1.4,3)..(1,3.8), lightred+1, EndArrow(TeXHead));
    draw( (0.8,1.6)..(0.4,2)..(0.8,2.4), lightred+1, EndArrow(TeXHead));
    draw( (0.8,3.6)..(0.4,4)..(0.8,4.4), lightred+1, EndArrow(TeXHead));
    draw( (0.2,1.4)..(0.6,1)..(0.2,0.6), blue+1.8, EndArrow(TeXHead));
    draw( (0.2,3.4)..(0.6,3)..(0.2,2.6), lightblue+1, EndArrow(TeXHead));
    draw( (0,2.8)..(-0.4,2)..(0,1.2), lightblue+1, EndArrow(TeXHead));
    draw( (0,4.8)..(-0.4,4)..(0,3.2), lightblue+1, EndArrow(TeXHead));
  \end{asy}
  \end{center}
  However, we assumed for contradiction the red and blue paths
  were part of the same trajectory, yet they clearly never meet.
\end{proof}

It remains to give a construction showing $3$ can be achieved.
There are many, many valid constructions.
One construction due to Danielle Wang is given here, who provided the following motivation:
``I was lying in bed and drew the first thing I could think of''.
The path is $CAHIFGDBAHEFGJBAC$ which visits $A$ three times.
\begin{center}
\begin{asy}
size(10cm);
defaultpen(fontsize(11pt));
pair A = (-2,2);
pair B = (2,2);
pair C = (-1,1);
pair D = (1,1);
pair E = (-1,-1);
pair F = (0,-1);
pair G = (1,-1);
pair H = (-2,-2);
pair I = (0,-2);
pair J = (2,-2);
pen gr = fontsize(14pt) + deepgreen;
draw(A--H, blue);
label("$2,9$", A--H, gr);
draw(A--C, blue);
label("$16$", A--C, gr);
draw(A--B, blue);
draw(B--D, blue);
draw(B--J, blue);
draw(B--A, blue);
label("$8,15$", B--A, gr);
draw(C--E, blue);
draw(C--D, blue);
draw(C--A, blue);
label("$1$", C--A, gr);
draw(D--C, blue);
draw(D--G, blue);
draw(D--B, blue);
label("$7$", D--B, gr);
draw(E--H, blue);
draw(E--F, blue);
label("$11$", E--F, gr);
draw(E--C, blue);
draw(F--I, blue);
draw(F--G, blue);
label("$5,12$", F--G, gr);
draw(F--E, blue);
draw(G--F, blue);
draw(G--J, blue);
label("$13$", G--J, gr);
draw(G--D, blue);
label("$6$", G--D, gr);
draw(H--I, blue);
label("$3$", H--I, gr);
draw(H--E, blue);
label("$10$", H--E, gr);
draw(H--A, blue);
draw(I--H, blue);
draw(I--J, blue);
draw(I--F, blue);
label("$4$", I--F, gr);
draw(J--B, blue);
label("$14$", J--B, gr);
draw(J--G, blue);
draw(J--I, blue);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, -dir(C));
dot("$D$", D, -dir(D));
dot("$E$", E, -dir(E));
dot("$F$", F, -dir(F));
dot("$G$", G, -dir(G));
dot("$H$", H, dir(H));
dot("$I$", I, dir(I));
dot("$J$", J, dir(J));

margin m = Margin(3,3);
pair[] trajectory = {C,A,H,I,F,G,D,B,A,H,E,F,G,J,B,A,C};
for (int i=0; i<trajectory.length-1; ++i) {
  draw(trajectory[i]--trajectory[i+1], red+1.4, m);
  draw(trajectory[i]--trajectory[i+1], red, EndArrow, m);
}
\end{asy}
\end{center}

\begin{remark*}
  As the above example shows it is possible to transverse
  an edge more than once even in the same direction, as in edge $AH$ above.
\end{remark*}

\end{document}
