XLIX OM - I - Zadanie 11

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

W turnieju tenisowym uczestniczyło $n$ graczy. Każdy rozegrał z każdym innym jeden mecz; nie było remisów. Udowodnić, że istnieje taki gracz $A$ , który każdego innego gracza $B$ pokonał bezpośrednio lub pośrednio, tzn. gracz $A$ wygrał z $B$ lub gracz $A$ pokonał pewnego zawodnika $C$ , który wygrał z tym graczem $B$ .

Rozwiązanie

Niech $A$ będzie tym uczestnikiem turnieju, który pokonał największą liczbę przeciwników. (Jeśli kilku zawodników odniosło jednakową maksymalną liczbę zwycięstw, wybieramy któregokolwiek z nich.) Twierdzimy, że wybrany w ten sposób gracz $A$ pokonał bezpośrednio lub pośrednio wszystkich innych zawodników.

Niech $B$ będzie dowolnym graczem, który wygrał z $A$ . Należy wykazać, że wśród wszystkich graczy $C_1,\ldots ,C_m$ pokonanych przez $A$ istnieje taki, który wygrał z $B$ .

Przypuśćmy, że tak nie jest. Oznacza to, że zawodnik $B$ pokonał graczy $C_1, \ldots ,C_m$ oraz jeszcze gracza $A$ — miałby więc na swoim koncie więcej zwycięstw niż zawodnik $A$ .

To jednak nie jest możliwe, skoro literą $A$ został oznaczony ten zawodnik, który odniósł najwięcej zwycięstw. Uzyskana sprzeczność kończy dowód.