MathDB

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) \equal{} 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) \equal{} f(x_2, x_3) \equal{} \cdots \equal{} f(x_{n\minus{}1}, x_n) \equal{} f(x_n, x_1) \equal{} 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\minus{}th player wins the game against the (i \plus{} 1)st and the n\minus{}th player wins against the first.

Problem Statement