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

\begin{document}
\title{Shortlist 2004 C2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 62}
\maketitle

\section*{Problem}
Let $n$ and $k$ be positive integers.
There are given $n$ circles in the plane.
Every two of them intersect at two distinct points,
and all points of intersection they determine are pairwise distinct.
No three circles have a point in common.
Each intersection point must be colored with one of $n$ distinct colors
so that each color is used at least once and exactly $k$ distinct colors
occur on each circle.
Find all values of $n\geq 2$ and $k$ for which such a coloring is possible.

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

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

\newpage

\section*{Solution}
Rephrasing:
\begin{quote}
  Given the graph $G = K_n$,
  we wish to color its edges with two of $n$ colors
  (possibly the same color) such that every color is used,
  and every vertex $v$ has exactly $k$ colors used at it.
\end{quote}

The answer is that:
\begin{itemize}
  \ii when $k=2$, only $n \in \{2,3\}$ are possible.
  \ii when $k=3$, any $n \ge k$ is permissible.
\end{itemize}
Let's prove this.
In what follows, $S(v)$ will denote the set of colors at a vertex $v$.

For $k=2$, the construction of $n=2$ and $n=3$ are routine:
\begin{itemize}
  \ii For $n = k = 2$, let $V(G) = \{v_1,v_2\}$.
  Then set $S(v_1) = S(v_2) = \{A,B\}$ and paint the edge with $AB$.
  \ii For $n = 3$ and $k = 2$, let $V(G) = \{v_1,v_2,v_3\}$.
  Then set $S(v_1) = \{A,B\}$, $S(v_2) = \{B,C\}$, $S(v_3) = \{C,A\}$
  and color $v_1v_2$ with $BB$, $v_2v_3$ with $CC$, $v_3v_1$ with $AA$.
\end{itemize}
\begin{claim*}
  For $k=2$, we have $n \le 3$.
\end{claim*}
\begin{proof}
  Assume $n > 3$.
  Each $S(v)$ is a two-element set.
  So we get a natural graph $\Gamma$ on the set of colors
  where the edges join two colors if they appear as some $S(v)$.
  This graph $\Gamma$ has the property any two edges intersect.
  This means it is either a $3$-cycle (hence $n=3$) or $K_{1,n-1}$.
  For $n > 3$, the latter case cannot work,
  since every color must appear in at least two $S(v)$'s.
\end{proof}

\begin{claim*}
  For $k \ge 3$ there is a construction for all $n \ge 3$.
\end{claim*}
\begin{proof}
  If $n=k=3$ let $V(G) = \{v_1,v_2,v_3\}$.
  Then set $S(v_1) = S(v_2) = S(v_3) = \{A,B,C\}$
  and color $v_1v_2$ with $AB$, $v_2v_3$ with $BC$, $v_3v_1$ with $CA$.

  Now suppose $n \ge 4$.
  Let $V(G) = \{v_1, v_2, \dots, v_n\}$
  and let the $n$ colors be $C_1$, $C_2$, \dots, $C_{n-1}$, $C_{\text{special}}$
  (breaking symmetry).
  We will create a construction with
  \begin{align*}
    S(v_1) &= \left\{ C_{\text{special}}, C_1, C_2 \right\} \\
    S(v_2) &= \left\{ C_{\text{special}}, C_2, C_3 \right\} \\
    &\vdotswithin{=} \\
    S(v_{n-2}) &= \left\{ C_{\text{special}}, C_{n-2}, C_{n-1} \right\} \\
    S(v_{n-1}) &= \left\{ C_{\text{special}}, C_{n-1}, C_1 \right\} \\
    S(v_n) &= S(v_1) = \left\{ C_{\text{special}}, C_1, C_2 \right\}.
  \end{align*}
  Assign colors to the following edges:
  \begin{itemize}
    \ii Assign $v_1v_2$ colors $C_{\text{special}} C_2$.
    \ii Assign $v_2v_3$ colors $C_{\text{special}} C_3$.
    \ii \dots
    \ii Assign $v_{n-2}v_{n-1}$ colors $C_{\text{special}} C_{n-1}$.
    \ii Assign $v_{n-1}v_{n}$ colors $C_{\text{special}} C_{1}$.
    \ii Assign $v_{n}v_{1}$ colors $C_1 C_2$.
  \end{itemize}
  Then assign $C_{\text{special}} C_{\text{special}}$ to all other edges.
\end{proof}

\begin{claim*}
  Given a construction for $(n,k)$
  we can get a construction for $(n+1, k+1)$.
\end{claim*}
\begin{proof}
  We do the following procedure.
  \begin{itemize}
  \ii Create a new color $C_{\text{new}}$ and add it to every $S(v)$.
  \ii Add a new vertex $v_{\text{new}}$.
  \ii Let $C_1$, \dots, $C_k$ be any old colors
  and let $v_1$, \dots, $v_k$ be vertices with $C_i \in S(v_i)$.
  \ii Set $S(v_{\text{new}}) = \{C_{\text{new}}, C_1, C_2, \dots, C_k\}$
  \ii The edges $v_{\text{new}}v_i$ are colored $C_iC_{\text{new}}$.
  \ii Any other edges are colored $C_{\text{new}} C_{\text{new}}$.
  \end{itemize}
  This completes the construction.
\end{proof}

\begin{remark*}
  I have to say I found most of the conditions in the problem
  rather unnatural to work with.
  For example, there is no real reason why the number of colors
  should be equal to the number of circles,
  and in fact the construction has to ``work around this''
  by breaking the symmetry somewhat in the first main claim.
\end{remark*}

\end{document}
