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.