淘汰賽

淘汰賽晉級表

淘汰賽係一種比賽嘅方式，體育比賽通常係由兩方對賽，其他比賽有機會係三隊或以上，輸咗嘅就淘汰出局，冇得繼續比賽，贏咗嘅就繼續晉級下一場比賽，對另一線勝出嘅對手，贏晒咁多場嘅就係冠軍。

好壞

淘汰賽嘅好處係容易實行，對主辦單位比較輕鬆； 壞處係比賽結果未必能夠反映參賽者嘅實力。

數學

如果跟住下面呢啲規則嚟計：

• 每場比賽都平均隨機咁分配參賽者。
• 每一位參賽者嘅實力都唔同，並且每次對賽，都一定係實力比較強嗰個贏。
• 總共有 $2^{n}$ 個人參賽。
• 每次由兩個人對賽。

咁就有以下嘅呢啲結論：

1. 要進行 $2^{n}-1$ 次對賽，先至完成整場淘汰賽。 因為每次對賽都會有 $1$ 個人出局，最後只剩低第一名 $1$ 個，即係途中有 $2^{n}-1$ 個人出局，所以要進行 $2^{n}-1$ 次對賽。
2. 要進行 $2^{n+1}-2$ 人次嘅對賽，先至完成整場淘汰賽。 因為每次對賽都有 $2$ 個人，即係 結論1 嘅兩倍 $=\ (2^{n}-1)\cdot 2\ =\ 2^{n+1}-2$。
3. 倒數第 $m$ 名，最多可以贏 $\lfloor lb(m)\rfloor$ 輪，$(m=1,2,3,...,2^{n})$。
4. 實力係 $k$ 嘅參賽者 $(k=0,1,2,...,2^{n}-1)$，至少贏 $r$ 輪嘅機率係 $2^{n-r}\cdot {\frac {C_{2^{r}-1}^{k}}{C_{2^{r}}^{2^{n}}}}$。
5. 結合 結論3 同 結論4 ，可以得出「實力係 k 嘅參賽者(倒數第 k+1 名)，贏佢可能贏嘅最多輪數」嘅機率。即係用 結論3 條式計到 $r=\lfloor lb(k+1)\rfloor$，再用 結論4 條式嚟計。

結論4 嘅證明：

首先要知道，所有對賽結果，都係由一開始分配參賽者嗰陣就決定哂。

想計實力係 k 嘅參賽者（下面叫： k號人) 嘅勝率：

• 如果 k 號人要喺第 1 輪贏，就要諗 k 號人同佢嘅對手組成嘅 2 人組。
• 如果 k 號人要喺第 2 輪贏，就要諗 k 號人同佢嘅對手組成嘅 2 人組，褪返去第一輪嗰陣，對應嘅 4 人組。
• 如果 k 號人要喺第 3 輪贏，就要諗 k 號人同佢嘅對手組成嘅 2 人組，褪返去第一輪嗰陣，對應嘅 8 人組。
• ...
• 如果 k 號人要喺第 r 輪贏，就要諗 k 號人同佢嘅對手組成嘅 2 人組，褪返去第一輪嗰陣，對應嘅 $2^{r}$ 人組。

同埋，褪返去第一輪嗰組(下面叫：嗰組)，唔可以出現強過 k 號人嘅人，如果唔係，k 號人就冇可能喺第 r 輪贏。

所以機率嘅計算條件係：

• 嗰組可以出現喺唔同位置，我地要計出所有可能嘅位置數量。 可能位置數 $=$ 所有人數 / 嗰組人數 $={\frac {2^{n}}{2^{r}}}=2^{n-r}$ 。
• 同時，喺所有 $2^{n}$ 個人入面抽 $2^{r}$ 個放喺嗰組，其中一定要有 k 號人，同埋其餘位置只可以係 0 至 k-1 號人。
  • 分母明顯係 $C_{2^{r}}^{2^{n}}$ ；
  • 分子：喺 0 至 k-1 號人，呢 $k$ 個人入面，抽 $2^{r}-1$ 個，放入嗰組嘅其餘位置，所以係 $C_{2^{r}-1}^{k}$。

所以 k 號人至少贏 ｒ 輪嘅機率係 $2^{n-r}\cdot {\frac {C_{2^{r}-1}^{k}}{C_{2^{r}}^{2^{n}}}}$。

睇埋

• 排列組合
• 機率