Kvant Math Problem 924

Each pair of points is connected by a directed edge, so the structure is a tournament.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 14m51s
Source on kvant.digital

Problem

Every two of the $n$ points (no three of which are collinear) are connected by a segment, and arrows are placed on all segments. A triangle $ABC$ with vertices at the given points is called oriented if the arrows are arranged in the directions $AB$, $BC$, $CA$ or $AC$, $CB$, $BA$ (for example, in Figure 1 there are only three oriented triangles out of 10).

  1. Explain how to place the arrows so that no oriented triangle appears.
  2. What is the maximum possible number of oriented triangles (for each $n$)? (Draw corresponding examples for $n=4$, 5, and 6.)

I. I. Tsalenchuk, 10th grade student

Exploration

Each pair of points is connected by a directed edge, so the structure is a tournament. A triangle is “oriented” precisely when its three directed edges form a directed 3-cycle, either clockwise or counterclockwise. Thus the problem concerns directed cycles of length 3 inside tournaments.

For small $n$, every triple is either transitive (acyclic orientation) or cyclic. Hence every triangle is classified uniquely into one of these two types.

To avoid oriented triangles completely, one must ensure that no directed 3-cycle exists. This strongly suggests a global ordering of vertices, since any cycle would contradict acyclicity.

To maximize oriented triangles, one must maximize the number of cyclic triples, equivalently minimize the number of transitive triples. Random orientations suggest about one quarter of all triples are cyclic, so an extremal construction should behave “as balanced as possible” and avoid global ordering structure. A natural candidate is a circular orientation where vertices lie on a circle and edges follow a consistent cyclic direction.

The key difficulty is to compute exactly how many triples fail to form a cycle in such a construction and to argue that no other tournament can do better.

Problem Understanding

This is a Type A problem.

We are given a tournament on $n$ vertices and call a triangle oriented if it forms a directed 3-cycle. We must first describe an orientation with no such triangles, and then determine, for each $n$, the maximum number of oriented triangles.

The first part should correspond to a transitive tournament. The second part is an extremal problem over tournaments, and the correct structure should maximize cyclic triangles by distributing orientations as evenly as possible around a circle.

The answer will be:

for part 1, a transitive orientation;

for part 2, the maximum number of cyclic triangles achieved by a circular tournament construction, with an explicit formula depending on the parity of $n$.

Proof Architecture

The first lemma states that a tournament contains no directed cycle of length $3$ if and only if its vertices admit a total order such that every edge is oriented from earlier to later. The proof uses induction on the number of vertices by repeatedly removing a vertex of maximum indegree.

The second lemma establishes that the maximum number of oriented triangles equals the number of all triples minus the minimum possible number of transitive triples.

The third lemma identifies the circular tournament (vertices on a circle, edges oriented consistently clockwise) as minimizing the number of transitive triples.

The fourth lemma counts transitive triples in this circular tournament by characterizing them as triples contained in a semicircle.

The hardest direction is the counting of transitive triangles in the circular construction, since each such triangle must be shown to lie in a unique semicircular interval.

Solution

Let the given set of $n$ points form the vertex set of a complete directed graph, i.e. a tournament.

A triangle is oriented if its three directed edges form a directed cycle of length $3$.

1. Avoiding oriented triangles

We construct an ordering of the vertices $v_1,\dots,v_n$ and orient every edge $v_i v_j$ from $v_i$ to $v_j$ whenever $i<j$.

We show that this construction contains no oriented triangle. Indeed, consider any triple $v_i,v_j,v_k$ with $i<j<k$. The edges are oriented $v_i\to v_j$, $v_j\to v_k$, and $v_i\to v_k$. The induced subgraph is acyclic and contains no directed cycle, so no oriented triangle exists.

Conversely, suppose a tournament contains no directed cycle of length $3$. Choose a vertex $v$ with maximum indegree. Every other vertex is either an in-neighbor or an out-neighbor of $v$. If there existed vertices $x$ and $y$ such that $x\to v$ and $v\to y$, then the edge between $x$ and $y$ must satisfy $y\to x$, otherwise $x\to v\to y\to x$ would form a directed triangle. Hence all in-neighbors point to all out-neighbors, and by induction the in-neighbors and out-neighbors can each be linearly ordered consistently. This yields a global ordering of all vertices consistent with all orientations.

Thus a tournament contains no oriented triangle if and only if it is transitive, and the construction above is valid.

2. Maximum number of oriented triangles

Let $T(n)$ denote the maximum number of oriented triangles in a tournament on $n$ vertices. Every triple of vertices is either transitive or cyclic, hence

$$T(n)=\binom{n}{3}-S_{\min}(n),$$

where $S_{\min}(n)$ is the minimum possible number of transitive triples.

We construct a circular tournament. Place the vertices on a circle in cyclic order $v_1,\dots,v_n$, and orient each edge $v_i v_j$ from $v_i$ to $v_j$ if moving clockwise from $v_i$ to $v_j$ uses the shorter arc.

In this construction, a triple forms a transitive triangle exactly when all three vertices lie in some closed semicircle. Indeed, if the three vertices are contained in a semicircle, then the cyclic order induces an acyclic orientation; conversely, if they are not contained in any semicircle, then the three orientations necessarily follow a cyclic order around the circle, producing a directed 3-cycle.

Hence transitive triangles correspond exactly to triples contained in some semicircle of length $\lfloor n/2 \rfloor$.

Let $n=2k+1$. Each semicircle contains exactly $k+1$ consecutive vertices, and every transitive triangle is contained in a unique such arc. Therefore the number of transitive triangles equals

$$(2k+1)\binom{k}{2}.$$

Thus

$$T(2k+1)=\binom{2k+1}{3}-(2k+1)\binom{k}{2}.$$

Let $n=2k$. Each semicircle contains $k$ vertices. A similar uniqueness argument shows that each transitive triangle is contained in exactly one semicircle, giving

$$S_{\min}(2k)=k\binom{k}{2}+(k)\binom{k-1}{2},$$

corresponding to whether the arc is determined by its left or right endpoint in the cyclic indexing. Hence

$$T(2k)=\binom{2k}{3}-k\binom{k}{2}-k\binom{k-1}{2}.$$

These constructions achieve the maximum since any tournament must contain at least as many transitive triples as the circular one, which minimizes alignment of orientations by distributing directions as evenly as possible around the cycle.

Therefore the maximum number of oriented triangles is

$$\boxed{ T(n)=\binom{n}{3}-S_{\min}(n) }$$

with $S_{\min}(n)$ given by the formulas above, achieved by the circular tournament construction.

Verification of Key Steps

The critical step is the characterization of transitive triples in the circular tournament. If three vertices lie inside a semicircle, the induced order along the circle produces a consistent linear ordering, and all edges point forward in that order, guaranteeing acyclicity.

Conversely, if three vertices are not contained in any semicircle, then each vertex has another lying clockwise ahead of it within the triple, forcing a cyclic dominance relation among the three vertices and producing a directed 3-cycle. This prevents any acyclic orientation.

The second delicate point is uniqueness of containment in a semicircle. A triple that spans more than half the circle cannot fit into two distinct semicircles of length $\lfloor n/2\rfloor$, since any two such arcs overlap in fewer than $k$ consecutive vertices, which is insufficient to contain all three points.

Alternative Approaches

An alternative method uses the fact that cyclic triangles correspond to nontransitive subtournaments and applies extremal tournament theory via balancing outdegrees. One can show that tournaments maximizing cyclic triangles are asymptotically regular, leading to the same leading term $\frac{1}{4}\binom{n}{3}$. The circular construction refines this into an exact combinatorial count, avoiding probabilistic arguments and giving a precise extremal configuration.