[Kombinatoryka] Mecze i ich zwycięzcy

[Swiety Mikolaj]

Mam zadanko kombinatoryczne i proszę o sprawdzenie, czy czegoś nie zgubiłem. Zadanie:
N zawodników rozgrywa mecze (każdy z każdym dokładnie jeden raz), nie ma remisów. Udowodnić, że zawsze można ich ustawić w kolejce tak, aby k-ty zawodnik wygrał z k+1-tym zawodnikiem.
Rozwiązanie:

Ukryta treść:    

Indukcja. Dla 2 graczy jest to oczywiste. Załóżmy, że można tak ustawić n graczy w kolejce. Niech teraz rozegrają oni mecze z n+1 zawodnikiem. Jeśli wygrał on wszystkie mecze, to stawiamy go na początku. Jeśli przegrał choć jeden mecz z zawodnikiem k-tym, to musi przegrać i z zawodnikiem k+1-tym, bo w przeciwnym razie otrzymujemy tezę od razu, stawiając go pomiędzy tymi właśnie zawodnikami. Stąd jeśli przegrał choć jeden mecz, to możemy założyć, że przegrał i z n-tym zawodnikiem. Ale i w tym wypadku otrzymujemy tezę, stawiając go na końcu kolejki.

[porfirion]

Jest poprawnie.

[Swiety Mikolaj]

thx