Turniej z braćmi

[Clevleen110]

W turnieju udział bierze \(\displaystyle{ 2^n}\) uczestników, w tym dwóch braci. Walka w systemie turniejowym, spośród zwycięzców danej tury wybiera się pary do kolejnej. Jakie jest prawdopodobieństwo, że bracia będą musieli ze sobą walczyć? Zakładamy, że prawdopodobieństwo wygranej dla dowolnej osoby w dowolnej parze wynosi \(\displaystyle{ \frac{1}{2}}\) .

[norwimaj]

Pewnie moje rozwiązanie nie jest najprostsze, ale akurat takie mi się udało wykombinować. Jest to coś w rodzaju metody zaburzania. Oznaczmy szukaną liczbę przez \(\displaystyle{ p_n,}\) gdzie \(\displaystyle{ n\ge1.}\) Ułożę dwa wzory rekurencyjne na \(\displaystyle{ p_n.}\) Ustalmy \(\displaystyle{ n>1.}\)

I. Całość uczestników jest podzielona na dwie grupy po \(\displaystyle{ 2^{n-1}}\) osób tak, że z każdej grupy wyjdzie jeden finalista. Albo bracia są w różnych grupach i mogą się spotkać tylko w finale, albo w tej samej i mogą się spotkać tylko przed finałem, stąd wzór:

\(\displaystyle{ p_n=\frac{2^{n-1}}{2^n-1}\cdot2^{-2(n-1)}+\frac{2^{n-1}-1}{2^n-1}\cdot p_{n-1}.}\)

II. Tym razem rozważamy przypadki, że albo bracia spotkają się od razu, albo nie, i wtedy muszą pokonać przynajmniej po jednym przeciwniku, żeby się spotkać.

\(\displaystyle{ p_n = \frac1{2^n-1}+\frac{2^n-2}{2^n-1}\cdot\frac1{2^2}\cdot p_{n-1}.}\)

Przyrównując oba wyniki obliczymy, że \(\displaystyle{ p_{n-1}=2^{-n+2}.}\) Zatem \(\displaystyle{ p_n=2^{-n+1}}\) dla \(\displaystyle{ n\ge1.}\)

[Gouranga]

Można też pomyśleć w drugą stronę tzn. pierwszy brat ma swoją stałą pozycję, zostaje \(\displaystyle{ 2^n-1}\) pozycji startowych dla drugiego brata
albo z prawdopodobieństwem \(\displaystyle{ \frac{1}{2^n-1}}\) trafi od razu do pary z bratem i nie muszą w ogóle wygrywać
albo z prawdopodobieństwem \(\displaystyle{ \frac{2}{2^n-1}}\) trafi do pary, której zwycięzca spotka się ze zwycięzcą pary brata i wtedy jeszcze każdy z nich musi wygrać
albo z prawdopodobieństwem \(\displaystyle{ \frac{2^2}{2^n-1}}\) trafi do jednej z par, skąd zwycięzca spotka się z kimś z czwórki brata po 2 rundach itd., ostatecznie może z prawdopodobieństwem \(\displaystyle{ \frac{2^{n-1}}{2^n-1}}\) trafić do drugiej połowy drzewa turniejowego i każdy z nich musi wygrać \(\displaystyle{ 2^{n-1}}\) rund żeby się spotkać w finale, stąd wzór:
\(\displaystyle{ P = \sum_{i=0}^{n-1} \frac{2^i}{2^n-1}\cdot \frac{1}{2^{2i}} = \sum \frac{1}{2^i(2^n-1)}}\)

[Clevleen110]

stąd wzór:
\(\displaystyle{ P = \sum_{i=0}^{n-1} \frac{2^i}{2^n-1}\cdot \frac{1}{2^{2i}} = \sum \frac{1}{2^i(2^n-1)}}\)

Skąd wzięło się \(\displaystyle{ \frac{1}{2^{2i}}}\) ?

[norwimaj]

Żeby się spotkali po \(\displaystyle{ i}\) rundach, to każdy z nich musi wygrać \(\displaystyle{ i}\) pierwszych rund.

[Nekro]

A dlaczego w \(\displaystyle{ \sum_{i=0}^{n=1}}\) \(\displaystyle{ n=1}\)?

[Gouranga]

tam nie ma \(\displaystyle{ n=1}\) tylko \(\displaystyle{ n-1}\) - tyle jest rund
skoro na początku masz \(\displaystyle{ 2^n}\) zawodników, po 1 rundzie zostanie \(\displaystyle{ 2^{n-1}}\), po i-tej rundzie \(\displaystyle{ 2^{n-i}}\) 2 zawodników zostanie po \(\displaystyle{ 2^{n-(n-1)}}\) bo kto wygra finał nas nie interesuje, dlatego najwyższe co rozważamy to \(\displaystyle{ n-1}\) czyli przypadek, gdzie obaj byli w różnych połowach drzewa i muszą się spotkać w finale