IMO 1989 LL POL79

Origin: POL

Problem

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) ̸= f(y, x) for all x, y (x ̸= 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 for every u \inU, v \inV . (ii) The elements of X can be labeled x1, . . . , xn so that f(x1, x2) = f(x2, x3) = \cdot \cdot \cdot = f(xn−1, xn) = f(xn, x1) = 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 ith player wins the game against the (i + 1)st and the nth player wins against the first.