Turniej ( omówienie )

Szansa na spotkanie braci wynosi 2/N niezależnie od kształtu drzewa turniejowego. Dowód:

Spotkanie braci musi zakończyć się porażką jednego z nich. Wystarczy więc policzyć dwie liczby: prawdopodobieństwo, że Alek w toku turnieju pokona Felka i prawdopodobieństwo, że Felek pokona Alka, po czym dodać te dwie liczby do siebie.

Policzmy prawdopodobieństwo, że Alek pokona Felka. Felek ma takie same szanse na wygranie turnieju jak każdy inny ( czyli jego szanse wynoszą 1/N ), i w takim wypadku nikt go nie pokona. W przeciwnym przypadku pokona go dokładnie jedna osoba i każdy z pozostałych zawodników ( są rozlosowywani po liściach, więc nierozróżnialni ) ma takie same szanse na zostanie pogromcą Felka (więc wynoszą one 1/(N-1) ).

Zatem Alek pokona Felka z prawdopodobieństwem (N-1)/N * (1/(N-1)), czyli po uproszczeniu 1/N. Pierwszy człon iloczynu to szansa na to, że Felek NIE wygra turnieju ( czyli ktokolwiek go pokona ). Drugi to szansa na to, że jego pogromcą będzie właśnie Alek.

Szansa na to, że Felek pokona Alka wynosi analogicznie 1/N, sumując otrzymujemy wynik 2/N.