Track / Stage 5 / 358 of 400 #958 of 1964

Problem 958

AIME late

Combinatorics Difficulty 5.9 Prove it

15. In a round-robin tournament with $n(n \geqslant 3)$ players, each pair of players plays one game, with no ties, and no player wins all their games. Prove: There must be three players $A$ , $B$ , $C$ , such that $A$ beats $B$ , $B$ beats $C$ , and $C$ beats $A$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

15. Each player corresponds to a point, resulting in a complete directed graph $K_{n}$ . By the problem's condition, no vertex has an outdegree of $n-1$ . By Corollary of Property 6: In $K_{n}$ , there exists a directed triangle. That is, there exist three players $A$ , $B$ , and $C$ , such that $A$ beats $B$ , $B$ beats $C$ , and $C$ beats $A$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.