# Problem of the Month (February 2020)

The problem used for Problem #1283 of the Macalester College Problem of the Week at my suggestion was the case K=4, N=8 of the following problem: Suppose K players enter a tournament, that the players are strictly ordered in ability, and that the better player wins 2/3 of the games. How should one construct a tournament of N games in series to maximize the chance of the best player winning the tournament. The answers are surprising, and can be found below.

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.

Here are the best known results for the generalization. Unless otherwise, stated, you should guess an ordering which is consistent with all the pairwise results. The pink results were found by Zach DeStefano.

Ranking All the Players in the Tournament
Players
23456
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.

Guessing Only Winner of Tournament
Players
234567
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.