ISL 1989 Problem 72

To each pair $(x, y)$ of distinct elements of a finite set $X$ a number $f(x, y)$ equal to 0 or 1 is assigned in such a way that $f(x, y) \neq f(y, x)$ $\forall x,y$ and $x \neq y.$ Prove that exactly one of the following situations occurs:

(i) $X$ is the union of two disjoint nonempty subsets $U, V$ such that $f(u, v) = 1$ $\forall u \in U, v \in V.$

(ii) The elements of $X$ can be labeled $x_1, \ldots , x_n$ so that $$f(x_1, x_2) = f(x_2, x_3) = \cdots = f(x_{n-1}, x_n) = f(x_n, x_1) = 1.$$

Alternative formulation:

In a tournament of n participants, each pair plays one game (no ties). Prove that exactly one of the following situations occurs:

(i) The league can be partitioned into two nonempty groups such that each player in one of these groups has won against each player of the other. (ii) All participants can be ranked 1 through $n$ so that $i-$ th player wins the game against the $(i + 1)$ st and the $n-$ th player wins against the first.