\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2005 C1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 6}
\maketitle
\section*{Problem}
A house has an even number of lamps distributed among its rooms
in such a way that there are at least three lamps in every room.
Each lamp shares a switch with exactly one other lamp,
not necessarily from the same room.
Each change in the switch shared by two lamps
changes their states simultaneously.
Prove that for every initial state of the lamps
there exists a sequence of changes in some of the switches
at the end of which each room contains lamps
which are on as well as lamps which are off.
\section*{Video}
\href{https://www.youtube.com/watch?v=HjR-g-AMhC8&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/HjR-g-AMhC8}}
\newpage
\section*{Solution}
First, we interpret the problem in a graph-theoretic language:
\begin{itemize}
\ii We interpret the problem as a graph $G$ with rooms
corresponding to vertices and switches with edges
(which may include self-loops).
\ii The only condition is that the minimal degree is at least $3$
(where self-loops contribute $2$ to the degree).
\ii The edges come in two colors,
which we call \emph{aligned} (switches between lamps of the same state)
or \emph{clashing} (switches between lamps of different states).
\ii We wish to \emph{label} the endpoints of each edge with $0$'s and $1$'s
(corresponding to ``off'' and ``on'') such that
\begin{itemize}
\ii aligned edges have $00$ or $11$ on their endpoint;
\ii clashing edges have $01$ or $10$ on their endpoint;
\ii every vertex has both $0$'s and $1$'s written
(we call such edges \emph{happy}).
\end{itemize}
\end{itemize}
For simplicity, we assume (WLOG) the graph $G$ is connected.
We will also assume $|V(G)| > 2$ (the case $|V(G)|=2$ is easy).
We describe an algorithm to do so:
it takes place in several steps.
\begin{itemize}
\ii \textbf{Step 1.}
Let $T$ be a spanning tree of $G$,
and root the tree $T$ by taking any non-leaf $v_0$.
Start by assigning all edges of $v_0$ in $T$
in such a way that $v_0$ is happy.
Then starting from $v_0$ and following
the pattern, label all edges of $T$
such that all vertices of $v_0$ become happy
except for the leaves
(which will only have one label).
\ii \textbf{Step 2.} Let $H$ be the set of leaves of $T$,
considered also an induced subgraph of $T$.
Every vertex of $H$ has at least one label.
If we take a spanning forest of $H$,
then we can proceed similarly as in Step 1
until there is at most one vertex in
each connected component of $H$ which is not happy.
\ii \textbf{Step 3.}
Consider the set $S$ of remaining unhappy vertices;
the set $S$ is an independent set, by construction.
Because the minimal degree is $3$,
they each have at least one more edge.
So they can be made happy.
\end{itemize}
We then label any remaining edges of $G$ arbitrarily;
since all vertices are happy already it doesn't matter how.
A cartoon of the process is given below.
\begin{center}
\begin{asy}
size(9cm);
draw(box((-4,-1), (4,1)), blue+dashed);
label("$H$", (4,1), dir(90), blue);
pair v0 = (0,4);
pair w1 = (-3,2);
pair w2 = (-1.5,2);
pair w3 = ( 1,2);
pair w4 = ( 3,2);
draw(v0--w1);
draw(v0--w2);
draw(v0--w3, lightgrey);
draw(v0--w4);
pair x1 = (-3,0);
pair x2 = (-1.5,0);
pair x3 = (-0.5,0);
pair x4 = (2,0);
pair x5 = (3,0);
draw(w1--x1, lightgrey);
draw(w2--x2);
draw(w3--x3, lightgrey);
draw(w3--x4);
draw(w4--x5, lightgrey);
dot(v0);
dot(w1);
dot(w2);
dot(w3);
dot(w4);
draw(x1..(-1,-0.5)..x3, blue);
draw(x3..(1,-0.5)..x4, paleblue);
draw(x2..(0,-0.8)..x5, blue);
dot(x1, blue);
dot(x2, blue);
dot(x3, blue);
dot(x4, blue);
dot(x5, blue);
draw(box(x4+(-0.2,-0.2), x4+(0.2,0.2)), red);
draw(box(x5+(-0.2,-0.2), x5+(0.2,0.2)), red);
defaultpen(fontsize(8pt));
void main(string s1, string s2, pair X, pair Y, pair t1, pair t2) {
label(s1, 0.85*X+0.15*Y, t1*dir(Y-X));
label(s2, 0.85*Y+0.15*X, t2*dir(Y-X));
}
main("0", "0", v0, w1, dir(-90), dir(-90));
main("1", "1", v0, w2, dir(10), dir(120));
main("0", "1", v0, w3, dir(-10), dir(-120));
main("0", "0", v0, w4, dir(90), dir(90));
main("1", "0", w1, x1, dir(90), dir(90));
main("0", "0", w2, x2, dir(90), dir(90));
main("0", "1", w3, x3, dir(90), dir(90));
main("1", "1", w3, x4, dir(90), dir(90));
main("1", "0", w4, x5, dir(90), dir(90));
label("1", x1, dir(-15)*2.5, blue);
label("1", x3, dir(195)*2.5, blue);
label("0", x3, dir(-15)*2.5, blue);
label("1", x4, dir(195)*2.5, blue);
label("1", x2, dir(-15)*2.5, blue);
label("0", x5, dir(195)*2.5, blue);
\end{asy}
\end{center}
The edges used in Step 1 and the tree $T$ itself are black;
the labeling is done from top to bottom.
The spanning forest of $H$ and its vertices are drawn in blue;
the labeling is done from left to right.
The vertices of $S$ are colored red and one more edge is used
for each of them (not shown).
Clashing edges are drawn in a lighter color than aligned edges.
\end{document}