\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{PUMaC 2015 C8}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 47}
\maketitle
\section*{Problem}
In a tournament with 2015 teams, each team plays every other team
exactly once and no ties occur.
Such a tournament is imbalanced if for every group of 6 teams,
there exists either a team that wins against the other 5
or a team that loses to the other 5.
If the teams are indistinguishable,
what is the number of distinct imbalanced tournaments that can occur?
\section*{Video}
\href{https://www.youtube.com/watch?v=YuGZ__XHtL8&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/YuGZ\_\_XHtL8}}
\newpage
\section*{Solution}
We need the following lemma:
\begin{lemma*}
[Twitch Lemma]
In a tournament if there is a $(k+1)$-cycle
then there is a $k$-cycle.
\end{lemma*}
\begin{claim*}
A tournament is balanced if there exists
two disjoint directed cycles,
or a directed cycle of length at least $6$.
\end{claim*}
\begin{proof}
In the former case,
the Twitch Lemma gives us two directed triangles,
which is bad.
In the latter case,
the Twitch Lemma gives us a directed 6-cycle,
which is bad.
\end{proof}
Using this one can show (many details omitted)
that the imbalanced tournaments
are given by the following list:
\begin{itemize}
\ii One fully ordered tournament
\ii $2013 \cdot 1$ tournaments
that consist of a directed $3$-cycle
and everything else being fully ordered.
\ii $2012 \cdot 1$ tournaments
that consist of a directed $4$-cycle
and everything else being fully ordered.
\ii $2011 \cdot 6$ tournament
that consist of a directed $5$-cycle
and everything else being fully ordered.
\end{itemize}
This gives an answer of $1 + 2013 + 2012 + 2011 \cdot 6 = 16092$.
\end{document}