Combinatoria
1989 Imo Longlists 1989 (1989)

1989 Imo Longlists 1989 P72

A cada par $ (x, y)$ de elementos distintos de un conjunto finito $ X$ se le asigna un número $ f(x, y)$ igual a 0 o 1 de tal manera que $ f(x, y) \neq f(y, x)$ $ \forall x,y$ y $ x \neq y.$ Demuestre que ocurre exactamente una de las siguientes situaciones: (i) $ X$ es la unión de dos subconjuntos disjuntos no vacíos $ U, V$ tales que $ f(u, v) = 1$ $ \forall u \in U, v \in V.$ (ii) Los elementos de $ X$ pueden etiquetarse como $ x_1, \ldots , 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.\] Formulación alternativa: En un torneo de n participantes, cada par juega un partido (sin empates). Demuestre que ocurre exactamente una de las siguientes situaciones: (i) La liga puede particionarse en dos grupos no vacíos tales que cada jugador en uno de estos grupos ha ganado contra cada jugador del otro. (ii) Todos los participantes pueden clasificarse del 1 al $ n$ de modo que el $ i-$ ésimo jugador gana el partido contra el $ (i + 1)-$ ésimo y el $ n-$ ésimo jugador gana contra el primero.

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados