Problem 8

8. A round-robin tournament was held among 13 players. Each player played one game against every other player. Each player won six games. How many triples (K,L,M) of players are there such that K beat L, L beat M, and M beat K?

Commentary: This was probably my favorite problem out of them all, as it certainly demanded my most effort.

My first thought was that I'd already solved this problem some months ago. It concerned the determinant of Vandermonde matrices, where cancellations of terms coincided with directed graphs which have no "triangles" $a→b→c→a$. I've attached the exercise and its proof on a separate paper. But though it turned out that that research wasn't going to directly help me here, I still expected the result to pan out relatively easily.

The first model for comparison I conceived of was the graph where $1→2,3,4,5,6,7$, $2→3,4,5,6,7,8$, $...$, $13→1,2,3,4,5,6$, whose triangles can be computed through one node then copied out by symmetry. Given that the problem asked for one specific number, I figured it would result that every directed graph on $2n+1$ for nodes each yielding an arrow to $n$ other nodes was isomorphic to this one for $n=6$. However, the solution wasn't making itself readily apparent, and though defaulting to a simpler case of $n=2$ allowed me to establish isomorphism with its appropriate graph, I was able to construct an explicit counterexample for $n=3$. This was startling, because now I realized this problem wouldn't be very trivial.

I began entertaining very far-flung ideas. Representing graphs as polynomials and considering their Grobner bases was probably the craziest. One persistent idea I had that I'm still curious about, was the semi-action (not actually a group action since it fails composition) of $S_{2n+1}$ on these graphs, where for example $(1 5 8)$ flips the arrows between $1$ and $5$, $5$ and $8$, and $8$ and $1$. This preserves the number of arrows projecting from any node, so I reasoned that in this case and perhaps generally it preserved the number of triangles. It took a bit of coding to handle higher-level examples show that it was not true in the general case, but I still held out some hope for it in this problem.

I had one big success before tripping over the actual solution below, in the form of a lemma which was never required. Its details are more complicated than that of the actual solution. I've also attached it.

Proof: Let $W$ be the tournament directed graph on $2n+1$ nodes inherited by the round-robin situation between $2n+1$ players for some $n$, where $a→b$ iff $a$ beat $b$ in the tournament. For any node $b$, observe how many pairs of nodes $a,c$ exist such that $a→b→c→a$. When $a→b$ and $b→c$ are assumed to hold there is merely $c→a$ to consider, hence it suffices to find the number of arrows projecting (1) from the set of nodes toward which $b$ points (what I call the image of $b$) (2) into the set of nodes pointing toward $b$. Since by definition no such arrow can project toward $b$, this is merely condition (1) so long as they don't point back into the image of $b$. Since there are $n$ nodes in the image, each projecting $n$ arrows, there are $n^2$ such arrows minus the amount projecting inward, which is merely the amount of arrows on an $n$ tournament directed graph $n(n-1)/2$, resulting in exactly $n(n+1)/2$ arrows. Multiply this by $2n+1$ nodes to get the raw number $n(n+1)(2n+1)/2$ of triples requested, and divide by $3$ to get the distinct number of $3$-cycles $n(n+1)(2n+1)/6$. For $2n+1=13$ this is respectively $273$ and $91$.$~\square$