Q72 Matemática  (IMO Longlists 1989)

cada par $(x,y)$ de elementos distintos de um conjunto finito $X$ um número $f(x,y)$ igual a 0 ou 1 é atribuído de tal forma que $f(x,y)neqf(y,x)$ $\forall x,y$ e $x\ne y.$ Prove que ocorre exatamente uma das seguintes situações: (i) $X$ é a união de dois subconjuntos não vazios disjuntos $U,V$ tal que $f(u,v)=1$ $\forall u\in U,v\in V.$ (ii) Os elementos de $X$ podem ser rotulados $x_1,\dots ,x_n$ de modo que $$f(x_1,x_2)=f(x_2,x_3)=\cdots =f(x_{n-1},x_n)=f(x_n,x_1)=1.$$ Formulação alternativa: Em um torneio de n participantes, cada dupla joga um jogo (sem empates). Prove que exatamente uma das seguintes situações ocorre: (i) A liga pode ser dividida em dois grupos não vazios, de modo que cada jogador de um desses grupos tenha vencido cada jogador do outro. (ii) Todos os participantes podem ser classificados de 1 a $n$ para que $i-$th jogador ganhe o jogo contra o $(i+1)$st e o $n-$th jogador ganhe contra o primeiro.