Knock-out
Problem
En bordtennisturnering for \(2^n\) deltakere har n omganger. Den er organisert som en knockout-turnering der to og to deltakere tilfeldig velges ut til å spille mot hverandre. Vinnerne av omgangen går videre til neste omgang. For hver ny omgang velges det tilfeldig hvem som skal spille mot hverandre. Siste omgang (n-te omgang) er finalen.
Før turneringen starter, peker vi ut to tilfeldig valgte spillere. Hva er sannsynligheten for at disse to kommer til å spille mot hverandre i en eller annen omgang i turneringen?
Vi antar i dette tankeeksperimentet at alle spillerne er like gode, og at sannsynligheten for å vinne og tape en kamp er like stor for alle spillerne i alle kampene.
Starthjelp
- Hva er sannsynligheten for at de to spillerne møtes i første runde?
- Hva er sannsynligheten for at begge spillerne går videre til andre runde?
- Hva er sannsynligheten for at de to spillerne møtes i andre runde?
Løsning
Vi kaller de to spillerne vi har pekt ut og vil følge med på, spiller A og spiller B. Uten å forandre på sannsynlighetene kan vi anta at spiller A trekkes ut først. Sannsynligheten for at B trekkes ut til å spille mot A, er da \(p=\frac 1{2^n-1}\).
Sannsynligheten for at B ikke trekkes ut til å spille mot A, er da \(1-\frac 1{2^n-1}\).
Sannsynligheten for at A vinner sin match, er den samme som sannsynligheten for at B vinner sin match, nemlig \(\frac12\).
Sannsynligheten for at B trekkes ut til å spille mot A, og at både A og B vinner sine matcher og går videre til neste runde, er \((1-\frac 1{2^n-1})\cdot\frac12 \cdot \frac12= \frac{2^n-2}{2^n-1}\cdot \frac14=\frac{2^{n-1}-1}{2 \cdot(2^n-1)}\)
I andre runde er antall spillere halvert, det vil si at det er igjen \(2^{n-1}\) spillere. Sannsynligheten for at A og B blir trukket til å spille mot hverandre i andre runde, er lik sannsynligheten for at begge går videre fra første runde, og at de trekkes ut i et par i andre runde: \(\frac{2^{n-1}-1}{2 \cdot(2^n-1)}\cdot \frac 1{(2^{n-1}-1)}=\frac1{2\cdot(2^n-1)}=\frac12p\)
Sannsynligheten for at de møtes i andre runde, er halvparten av sannsynligheten for at de møtes i første runde.
I tredje runde er antall deltakere på nytt halvert, og med tilsvarende resonnement kan vi finne at sannsynligheten for at de møtes i tredje runde, er halvparten av sannsynligheten for at de møtes i andre runde. Og sannsynligheten for at de møtes i n-te runde, er halvparten av sannsynligheten for at de møtes i runde nummer n – 1.
Sannsynligheten for at A og B møtes til match i første runde eller i andre runde eller i tredje runde … eller i n-te runde, er da:
\(\begin{align} p+\frac12p+\frac14p+...+\frac1{2^{n-1}}p&=\\ \frac1{2^n-1}(\frac11+\frac12+\frac14+...+\frac1{2^{n-1}})&=\\ \frac1{2^n-1}\cdot1\cdot\frac{(\frac12)^n-1}{\frac12 -1}&=\\ \frac1{2^n-1}\cdot\frac{2^n-1}{2^{n-1}}&=\\ \frac1{2^{n-1}}& \end{align}\)
Så sannsynligheten for at de to spillerne møtes en eller annen gang under turneringen, hvis det er \(2^n\) spillere, er \(\frac1{2^{n-1}}\).
Ressursen er utviklet av NRICH