\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}
