
C3. $N$ teams take part in a league. Every team plays every other team exactly once during the league, and receives 2 points for each win, 1 point for each draw, and 0 points for each loss. At the end of the league, the sequence of total points in descending order $\mathcal{A}=\left(a_{1} \geq a_{2} \geq \cdots \geq a_{N}\right)$ is known, as well as which team obtained which score. Find the number of sequences $\mathcal{A}$ such that the outcome of all matches is uniquely determined by this information.

## United Kingdom, Dominic YeO


Solution. The required number is the $(N+1)$ st Fibonacci number $F_{N+1}$, where $F_{1}=F_{2}=1$, and $F_{k}=F_{k-1}+F_{k-2}, k \geq 3$; explicitly, $F_{k}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{k}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{k}$.

In the sequel, a tournament is a collection of all game results. We say that a tournament is deterministic if its score sequence determines it uniquely. We always assume that the teams in a tournament are enumerated $t_{1}, t_{2}, \ldots, t_{N}$ in a non-decreasing order of their scores $a_{1} \geq a_{2} \geq$ $\cdots \geq a_{n}$.

The argument is in three stages. First, we describe some deterministic tournaments and their score sequences. Then, we show no other tournament is deterministic. Finally, we enumerate the obtained tournaments.

Step 1. Let $\sigma$ be some collection of disjoint pairs of adjacent elements of $\{1, \ldots, N\}$. Now we define a tournament $T^{\sigma}$ by letting $t_{i}$ and $t_{i+1}$ make a draw if $(i, i+1) \in \sigma$, and letting $t_{i}$ win $t_{j}$, where $ia_{j} \Longleftrightarrow t_{i} \rightarrow t_{j}$. Indeed, otherwise there would exist either a pair $(i, j)$ with $t_{j} \rightarrow t_{i}$ yet $a_{i} \geq a_{j}$, or a pair $(i, j)$ with $t_{i} \leftrightarrow t_{j}$ yet $a_{i}>a_{j}$. In both cases, there is a team $t_{k}$ whose result in the game with $t_{j}$ is strictly better than that with $t_{i}$. Therefore, the triple $\left(t_{i}, t_{j}, t_{k}\right)$ violates the Lemma.

(ii) There are no three indices $i, j, k$ with $a_{i}=a_{j}=a_{k}$. Otherwise, by (i) we get $t_{i} \leftrightarrow t_{j} \leftrightarrow t_{k} \leftrightarrow$ $t_{i}$, so $\left(t_{i}, t_{j}, t_{k}\right)$ violates the Lemma.

Now, given a deterministic tournament $T$, we denote by $\sigma$ the set of all pairs $(i, j)$ with $a_{i}=a_{j}$. By property (ii), these pairs are disjoint, and, by monotonicity, each consists of consecutive indices. Therefore, property (i) yields $T=T^{\sigma}$, as desired.

Step 3: Let $\mathcal{B}_{N}$ be the set of suitable $\sigma$ s corresponding to $N$. It remains just to count $B_{N}=$ $\left|\mathcal{B}_{N}\right|$. There are natural bijections between $\left\{\sigma \in \mathcal{B}_{N}:(1,2) \notin \sigma\right\}$ and $\mathcal{B}_{N-1}$, and between $\left\{\sigma \in \mathcal{B}_{N}:(1,2) \in \sigma\right\}$ and $\mathcal{B}_{N-2}$.

Thus $B_{N}=B_{N-1}+B_{N-2}$. Now, it is clear that $B_{1}=1$, and after a bit of thought $B_{2}=2$. So $B_{N}=F_{N+1}$, the $(N+1)$ st Fibonacci number.

Remark. One may perform Steps 2 and 3 in many different ways. Although the general scheme preserves, the arguments may vary. Below we list several such arguments.

Alternative approaches to Step 2. (a) The Lemma from the Solution above may be split into cases. E.g., one may list explicitly sub-tournaments on three teams that never appear in a deterministic tournament, namely: (1) $x \rightarrow y, y \rightarrow z, z \rightarrow x$; (2) $x \leftrightarrow y, y \leftrightarrow z, z \leftrightarrow x$; (3) $x \leftrightarrow y, y \leftrightarrow z, z \rightarrow x$; and (4) $y \rightarrow x, z \rightarrow y, x \leftrightarrow z$. (Indeed, the sub-tournaments (1) and (2) provide the same input to the score sequence, and so do (3) and (4).) After that, a similar analysis may be performed in order to show that the only tournaments having no sub-tournaments of the forms (1)-(4) are those described in Step 1.

(b) An alternative combinatorial description of a deterministic tournament may also be obtained as follows. We realize a tournament as a directed (multi)graph on $[N]=\{1,2, \ldots, N\}$, where each pair of vertices are connected by two directed edges. These are both directed from loser to winner, else for a draw, we assign one edge in each direction. In this realization, the score sequence lists the in-degrees of the vertices.

Now, if the digraph includes a simple cycle with length at least 3 , then one may obtain an alternative tournament with the same score sequence by reverting all arrows in the cycle. Thus, the only cycles a graph of a deterministic tournament may have are of length 2 (and correspond to draws). Thus, one may see that no team draws with two others (as they would form a cycle of length 3), and every pair which draws plays identically to each other team. So, after "de-cloning" such pairs, we get a usual transitive tournament, which establishes Step 2.

Such framework may also help in performing Step 1.

Alternative approach to Step 3. The number of relevant score sequences including exactly $k$ pairs is $\binom{N-k}{k}$, for each $k=0,1, \ldots,\lfloor N / 2\rfloor$. (Think about choosing $k$ non-adjacent elements from $[N-1]$.)

Thus

$$
\begin{aligned}
B_{N} & =\sum_{k=0}^{\lfloor N / 2\rfloor}\binom{N-k}{k}=\sum_{k=0}^{\lfloor N / 2\rfloor}\left[\binom{N-k-1}{k-1}+\binom{N-k-1}{k}\right] \\
& =\sum_{k=0}^{\lfloor N / 2\rfloor}\binom{(N-2)-(k-1)}{k-1}+\sum_{k=0}^{\lfloor N / 2\rfloor}\binom{(N-1)-k}{k} \\
& =\sum_{k=0}^{\lfloor N / 2\rfloor}\binom{(N-2)-k}{k}+\sum_{k=0}^{\lfloor N / 2\rfloor}\binom{(N-1)-k}{k} \\
& =B_{N-2}+B_{N-1}
\end{aligned}
$$

and then one can finish as before.

It is worth mentioning that the obtained relation $\sum_{k}\binom{N-k}{k}=F_{N+1}$ is quite known, as well as the whole enumeration of partitions of $[N]$ into singletons and pairs of consecutive elements.
