\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2002 C7}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 18}
\maketitle
\section*{Problem}
Among a group of $120$ people, some pairs are friends.
A weak quartet is a set of four people containing
exactly one pair of friends.
What is the maximum possible number of weak quartets ?
\section*{Video}
\href{https://www.youtube.com/watch?v=4AxsoRBAYE0&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/4AxsoRBAYE0}}
\newpage
\section*{Solution}
The answer is $4769280$
achieved when the graph $G$ is five
disjoint copies of $K_{24}$.
The following claim reduces the problem to an annoying
(but routine) calculation:
\begin{claim*}
The optimum is achieved when $G$ consists
of the disjoint union of several cliques.
\end{claim*}
\begin{proof}
The proof goes by Zykov symmetrization.
Assume that $G$ is chosen so the number of
weak quartets is maximized.
Throughout the process, we annotate every vertex $v$ of $G$
with the number of weak quartets that $G$ is in, say $n(v)$.
Now the main observation is that:
if $n(v) \ge n(v')$,
then deleting $v'$ and replacing it with a clone of $v$
changes the number of weak quartets in the graph
by $n(v) - n(v')$.
Indeed,
\begin{itemize}
\ii Any weak quartet that involved $v'$ but not $v$ is destroyed;
\ii Any weak quartet that involved $v$ but not $v'$ is cloned;
\ii Any weak quartet that involved both $v$ and $v'$
is unaffected (as is any weak quartet
which involved neither).
\end{itemize}
Since $G$ was picked maximally,
that means in fact $n(v) = n(v')$
for any $v$ and $v'$ in the same connected component of $G$.
Hence we can do the cloning operation between
any pair of adjacent vertices $v$ and $v'$,
with no change to the number of weak quartets.
Moreover, doing so won't change $n(w)$
for any other vertices $w$ which remain in the same
connected component as the cloned $v$.
After all, if it did, then we could perform
the operation in a way that strictly increases
the number of weak quartets,
contradicting again the maximality of $G$.
So, for each component $C$ of $G$,
we pick any vertex $v$ and clone it everywhere.
This could break off $C$ into multiple components, which is okay;
we then handle those components by the same procedure later on.
Repeating this procedure several times we eventually
arrive at $G$ a disjoint union of cliques.
\end{proof}
The rest of the calculation is only outlined below.
If $G$ has cliques of size $a_1$, \dots, $a_n$
then the number of weak quartets is exactly
\[
\sum_1^n \binom{a_i}{2}
\sum_{\substack{1 \le j < k \le n \\ j,k \ne i}} a_j a_k
\]
and a calculation shows we want these to be as close as equal
as possible.
Up to integer rounding issues,
this means we have
\[ n \cdot \binom{120/n}{2} \binom{n-1}{2} \cdot \left( \frac{120}{n}
\right)^2 \]
which turns out to be maximal at $n=5$
giving the answer earlier.
\end{document}