Knock-out

Stikkord: Sannsynligjet

Mange par som er klare til å spille bordtennis.

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.

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?

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

Knock-out

Problem

Starthjelp

Løsning