Kvant Math Problem 478

Represent the tournament by a directed complete graph.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 16m46s
Source on kvant.digital

Problem

In a volleyball tournament, every pair of teams played exactly one match against each other.

  1. Prove that if, for any two teams, there exists a third team that has defeated both of them, then the number of teams is at least seven.
  2. Construct an example of such a tournament with seven teams.
  3. Prove that if, for any three teams, there exists a team that has defeated all three, then the number of teams is at least fifteen.

S. V. Konyagin

Moscow Mathematical Olympiad (XL, 1977, grades 8–10)

Exploration

Represent the tournament by a directed complete graph. For a vertex $v$, let

$$N^-(v)={u:u\to v},$$

and let $d^-(v)=|N^-(v)|$ be the indegree of $v$.

The condition in part (1) says that every pair of vertices has a common predecessor. The condition in part (3) says that every triple of vertices has a common predecessor.

The main tool is counting pairs or triples inside the predecessor sets $N^-(v)$.

Problem Understanding

Part (1) asks for the smallest possible number of teams if every pair of teams is defeated by some third team.

Part (2) asks for a tournament on seven teams having this property.

Part (3) asks for the smallest possible number of teams if every triple of teams is defeated by some fourth team.

Proof Architecture

For part (1), every pair of vertices must occur in at least one predecessor set $N^-(v)$. Counting such pairs yields an inequality involving the indegrees.

For part (2), a cyclic tournament on the residues modulo $7$ provides the required example.

For part (3), the triple condition implies that the predecessor set of every vertex itself satisfies the condition from part (1). Applying part (1) inside those predecessor sets gives a lower bound on every indegree, which is incompatible with a tournament on only $14$ vertices.

Solution

Part (1)

Assume that for every pair of teams there exists a team that defeated both.

Every unordered pair of vertices ${x,y}$ is contained in $N^-(v)$ for at least one v