Is It Shapeist To Disallow Triangles?

Represent each team as a vertex of a graph, and trace an arrow from $A$ to $B$ , $A\rightarrow B$ , if team $A$ beat team $B$ in the corresponding game. If the game ended in a draw we do not trace any arrow.

We will use graph theory terminology. Thus, in this problem, each vertex has outdegree 3, and there is no 3-cycle.

Since each vertex has outdegree 3, we can take a vertex $A_1$ with indegree at least 3. Suppose that there are arrows from $A_2, A_3, A_4$ to $A_1$ , and suppose that there are arrows from $A_1$ to $A_5, A_6, A_7$ , then the vertices $A_1, A_2, A_3, A_4, A_5, A_6, A_7$ are pairwise distinct.

Since $A_5A_6A_7$ is not a directed 3-cycle we note that one of $A_5, A_6, A_7$ didn't beat the two other teams. W.l.o.g suppose that $A_5$ didn't beat $A_6$ and $A_5$ didn't beat $A_7$ . Since $A_5$ won exactly three times, there are teams $A_8, A_9, A_{10}$ who were beaten by $A_5$ .

It is clear that sets $\{A_8, A_9, A_{10}\}$ and $\{A_1, A_5, A_6, A_7\}$ are disjoint. Now we will prove that $\{A_8, A_9, A_{10}\}$ and $\{A_2, A_3, A_4\}$ are disjoint. Suppose, for example, that $A_8=A_2$ , then we have the 3-cycle $A_2\rightarrow A_1\rightarrow A_5\rightarrow A_8=A_2$ which is not possible. Therefore the sets $\{A_8, A_9, A_{10}\}$ and $\{A_2, A_3, A_4\}$ are disjoint, and this means that there are at least 10 teams, i.e. $n\geq 10$ .

Let's construct an example for each $n\geq 10$ . Consider a circle with circumference $n$ and place the vertices $A_1, A_2, \ldots, A_n$ on that circle such that all the small arcs have length 1. From each $A_i$ trace three arrows to the vertices $A_{i+1}, A_{i+2}, A_{i+3}$ (indexes are considered module $n$ ). Suppose that this directed graph has a 3-cycle $A_i\to A_j \to A_k\to A_i$ , thus the complete cirumference is divided into three arcs: $A_iA_j, A_jA_k, A_kA_i$ , this is a contradiction since the length of the circumference is $n\geq 10$ and the length of each arc is 1, 2 or 3.

Therefore, the possible values of $n$ are $\{10,11,12,\ldots, 100\}$ , thus the answer is $100-10+1=91$ .