XLIX OM - I - Zadanie 11

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.

Komentarze

Dodaj nową odpowiedź