This month's problem is to generalize this further. What if the tournament's purpose is not just to specify a winner, but to order all the players in ability. What tournament maximizes the probability that we are correct?
For example, if there are K=3 players and N=2 games, the best we can do is A vs B and (regardless of who wins the first time) A vs C, and then to guess an ordering that is consistent with those results. 1/3 of the time, A will be the middle player in ability, and then we will guess correctly if both games are accurate. 2/3 of the time, A will be the best or worst player, and then will guess half the time both games are accurate. So we will succeed with probability (1/3)(2/3)2+(2/3)(1/2)(2/3)2=8/27.
| Players | |||||||
|---|---|---|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 | |||
| G a m e s | 0 | 1/2 = 50% | 1/6 = 16.7% | 1/24 = 4.17% | 1/120 = .833% | 1/720 = .139% | |
| 1 | A vs B 2/3 = 66.7% | A vs B 2/9 = 22.2% | A vs B 1/18 = 5.56% | A vs B 1/90 = 1.11% | A vs B 1/540 = .185% | ||
| 2 | A vs B 2/3 = 66.7% | A vs B, A vs C 8/27 = 29.6% | A vs B, A vs C 2/27 = 7.41% | A vs B, A vs C 2/125 = 1.48% | A vs B, A vs C 1/405 = .247% | ||
| 3 | A vs B best-of-3 20/27 = 74.1% | A vs B, A vs C if necessary, B vs C 28/81 = 34.6% | A plays everyone 8/81 = 9.88% | A vs B, A vs C, A vs D 8/405 = 1.98% | A vs B, A vs C, A vs D 4/1215 = .329% | ||
| 4 | A vs B best-of-3 20/27 = 74.1% | A vs B, A vs C if A wins 0 or 2, B vs C otherwise, A vs B twice 88/243 = 36.2% | A plays everyone 2 with equal records play 32/243 = 13.2% | A plays everyone 32/1215 = 2.63% | A vs B, A vs C, A vs D, A vs E 16/3645 = .439% | ||
| 5 | A vs B best-of-5 64/81 = 79.0% | A vs B, A vs C if A wins 0 or 2, B vs C best-of-3 otherwise, A vs B if same result as last time, A vs C twice if different result, A vs B again if same result as last time, B vs C 296/729 = 40.6% | A plays everyone 2 with equal records (say B and C) play if necessary, B plays D 112/729 = 15.4% | A plays everyone 2 with equal records play 16/405 = 3.95% | A plays everyone 64/10935 = .585% | ||
| 6 | A vs B best-of-5 64/81 = 79.0% | it's complicated 928/2187 = 42.4% | A plays everyone if A wins 0 or 3, B vs C and B vs D and if necessary, C vs D otherwise, 2 with equal records play and closest to A plays A twice more 352/2187 = 16.1% | A plays everyone 2 with equal records play if possible, 2 with equal records play otherwise, 2 with equal records against A play for the first time 64/1215 = 5.27% | A plays everyone 2 with equal records play 256/32805 = .780% | ||
| 7 | A vs B best-of-7 1808/2187 = 82.7% | it's complicated 2944/6561 = 44.9% | it's complicated 1136/6561 = 17.3% | ? | A plays everyone 2 with equal records play another 2 with equal records play 1024/98415 = 1.04% | ||
Piotr Zieliński found most of the solutions for the original problem, shaded in light green below.
| Players | |||||||
|---|---|---|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 | 7 | ||
| G a m e s | 0 | guess 1/2 = 50% | guess 1/3 = 33.3% | guess 1/4 = 25% | guess 1/5 = 20% | guess 1/6 = 16.7% | guess 1/7 = 14.2% |
| 1 | A vs B 2/3 = 66.7% | A vs B 4/9 = 44.4% | A vs B 1/3 = 33.3% | A vs B 4/15 = 26.7% | A vs B 2/9 = 22.2% | A vs B 4/21 = 19.0% | |
| 2 | A vs B 2/3 = 66.7% | A vs B winner vs C 14/27 = 51.9% | A vs B winner vs C 7/18 = 38.9% | A vs B winner vs C 14/45 = 31.1% | A vs B winner vs C 7/27 = 25.9% | A vs B winner vs C 2/9 = 22.2% | |
| 3 | A vs B best-of-3 20/27 = 74.1% | A vs B winner vs C twice (C loses ties) 44/81 = 54.3% | A vs B, C vs D winners play 4/9 = 44.4% | A vs B, C vs D winners play 16/45 = 35.6% | A vs B, C vs D winners play 8/27 = 29.6% | A vs B, C vs D winners play 16/63 = 25.4% | |
| 4 | A vs B best-of-3 20/27 = 74.1% | A vs B winner vs C best-of-3 140/243 = 57.6% | A vs B winner vs C and D winners play 38/81 = 46.9% | A vs B winner vs C, D vs E winners play 52/135 = 38.5% | A vs B winner vs C, D vs E winners play 26/81 = 32.1% | A vs B winner vs C, D vs E winners play 52/189 = 27.5% | |
| 5 | A vs B best-of-5 64/81 = 79.0% | A vs B, winner (say A) vs C if A wins, B vs C, winner vs A twice (A wins ties) if C wins, A vs C again if A wins, A vs C twice (A wins ties) if C wins, B vs C twice (C wins ties) 148/243 = 60.9% | A vs B, C vs D winners play best-of-3 40/81 = 49.4% | A vs B, winner (say A) plays C if A wins, A vs D, A vs E, and winners play if A loses, A vs D if A wins, A vs E and winner plays C if A loses, C vs E and winner plays D 1496/3645 = 41.0% | A vs B, C vs D, winners play winner plays winner of E vs F 28/81 = 34.6% | A vs B, C vs D, winners play winner plays winner of E vs F 8/27 = 29.6% | |
| 6 | A vs B best-of-5 64/81 = 79.0% | A vs B best-of-3 winner vs C rest (C loses ties) 1376/2187 = 62.9% | A vs B (say A wins) A vs C, A vs D if A wins both, B plays C, winner plays A twice (A wins ties) otherwise, winners play best-of-3 1124/2187 = 51.4% | it's complicated 944/2187 = 43.2% | A vs B, C vs D winners play (say A wins) A plays E, A plays F, winners play 268/729 = 36.8% | A vs B, C vs D, winners play to get to final E vs F, winner plays G to get to final 20/63 = 31.7% | |
| 7 | A vs B best-of-7 1808/2187 = 82.7% | it's complicated 4304/6561 = 65.6% | A vs B, C vs D winners (say A and C) play twice if split, A vs C best-of-3 if A sweeps, B vs D winner plays A twice (A wins ties) 128/243 = 392/729 = 53.8% | it's complicated 986/2187 = 45.1% | it's complicated 7624/19683 = 38.7% | A vs B, C vs D winners play (assume A wins) E vs F, winner plays A winner plays winner of A and G 572/1701 = 33.6% | |
| 8 | A vs B best-of-7 1808/2187 = 82.7% | it's complicated 13256/19683 = 67.3% | it's complicated 10936/19683 = 55.6% | it's complicated 3085/6561 = 47.0% | it's complicated 296/729 = 40.6% | it's complicated 243823/688905 = 35.4% | |
| 9 | A vs B best-of-9 16832/19683 = 85.5% | it's complicated 13664/19683 = 69.4% | it's complicated 3776/6561 = 57.2% | it's complicated 143816/295245 = 48.7% | it's complicated 124736/295245 = 42.2% | A vs B, C vs D winners play (assume A beats C) C plays E, F plays G, winners play winner plays A best-of-3 5680/15309 = 37.1% | |
| 10 | A vs B best-of-9 16832/19683 = 85.5% | it's complicated 41936/59049 = 71.0% | it's complicated 104984/177147 = 59.3% | it's complicated 447236/885735 = 50.5% | it's complicated 1164556/2657205 = 43.8% | it's complicated 1436096/3720087 = 38.6% | |
| 11 | A vs B best-of-11 640/729 = 87.8% | it's complicated 128848/177147 = 72.7% | it's complicated 4000/6561 = 61.0% | it's complicated 276712/531441 = 52.1% | it's complicated 3616384/7971615 = 45.4% | it's complicated 4470392/11160261 = 40.1% | |
| 12 | A vs B best-of-11 640/729 = 87.8% | it's complicated 1182112/1594323 = 74.1% | it's complicated 332528/531441 = 62.6% | it's complicated 4276042/7971615 = 53.6% | it's complicated 11194744/23914845 = 46.8% | it's complicated 13874431/33480783 = 41.4% | |
If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 2/1/20.