Can You Construct The Optimal Tournament?

Riddler Express

You colour any cells you like in an empty $4 \times 4$ grid. Then a $2 \times 2$ piece is secretly cut out and shown to you without rotating it, and you must say where it came from (top-left, top-middle, …, bottom-right: nine positions). Can you design a colouring for which the piece always reveals its position?

The Riddler, FiveThirtyEight, July 19, 2019(original post)

Solution

A $2 \times 2$ piece can be cut from nine positions: its top-left corner sits at any of the $3 \times 3$ interior corners of the grid. You win exactly when those nine $2 \times 2$ windows show nine different patterns, so that no two positions can be confused. Since a $2 \times 2$ window has $2^4 = 16$ possible colourings and you need only nine distinct ones, there is plenty of room, and such colourings exist.

The prettiest is the “donut”: colour the central $2 \times 2$ block and leave the rest blank. $$\begin{array}{cccc} \cdot & \cdot & \cdot & \cdot \\ \cdot & \bullet & \bullet & \cdot \\ \cdot & \bullet & \bullet & \cdot \\ \cdot & \cdot & \cdot & \cdot \end{array}$$ Every cut catches a different corner of the central block: the bottom-right window sees a coloured cell in its top-left, the top-left window sees one in its bottom-right, the centre window is fully coloured, an edge window shows two coloured cells along one side, and so on. All nine windows differ. $$\boxed{\text{Yes; the central } 2\times 2 \text{ ``donut'' is one such colouring.}}$$

The computation

Encode the test directly: over all $2^{16}$ colourings of the grid, extract the nine $2 \times 2$ windows and count the colourings whose windows are all distinct. The donut should be one of them, and the total count is a check against the official’s tally.

def windows(g):                          # g: 16-bit grid, cell (i,j) = bit 4*i+j
    out = []
    for r in range(3):
        for c in range(3):
            w = 0
            for di in range(2):
                for dj in range(2):
                    w = (w << 1) | ((g >> (4 * (r + di) + (c + dj))) & 1)
            out.append(w)
    return out

count = sum(len(set(windows(g))) == 9 for g in range(1 << 16))
print("colourings that always reveal the position:", count)

donut = 0
for (i, j) in [(1, 1), (1, 2), (2, 1), (2, 2)]:
    donut |= 1 << (4 * i + j)
print("donut works:", len(set(windows(donut))) == 9)
# colourings that always reveal the position: 6188
# donut works: True

There are $6{,}188$ winning colourings, the donut among them.

Riddler Classic

Players are ranked by ability, but the order is unknown; the better player wins any game two-thirds of the time. Construct a tournament (a fixed schedule of games) that maximises the chance the best player ends up champion. Find the best tournament for four players in four games and for five players in five games. Extra credit: the general pattern.

The Riddler, FiveThirtyEight, July 19, 2019(original post)

Solution

The best player wins each of their games with probability $\tfrac23$, so to crown the best player you want a schedule in which the best player, wherever they happen to be seeded, has to win as few games as possible while still being tested against the field. Since the seeding is unknown, the right measure is the chance the best player is champion averaged over all equally-likely seat assignments. With one extra game beyond the simple bracket, you can do better than the standard knockout.

Four players, four games. Seed the players $A, B, C, D$. Play $A$ versus $B$; the winner then plays both $C$ and $D$; finally the winners of those two games meet for the title (if the same player won both, that player is champion). The best player, in whatever seat, has a shorter expected road to the title than in the three-game bracket, and the chance they win rises to $$\frac{38}{81} \approx 46.9\%,$$ above the simple bracket’s $4/9 \approx 44.4\%$.

Five players, five games. The optimal schedule is adaptive. Play $A$ versus $B$ and call the winner $A$; then $A$ plays $C$. If $A$ wins, $A$ plays $D$ and $E$ and the two winners meet for the title. If $A$ loses to $C$, then $A$ plays $D$: if $A$ wins, $A$ plays $E$ and that winner faces $C$ for the title; if $A$ loses, $C$ plays $E$ and that winner faces $D$. The best player is champion $$\frac{1496}{3645} \approx 41.0\%$$ of the time.

The computation

Encode each schedule exactly and average over seatings. Fix the skill order ($0$ is best, then $1, 2, 3, \ldots$), assign the players to the seats by every permutation, and enumerate all game outcomes with their exact $\tfrac23 / \tfrac13$ weights, accumulating the probability that the best player (skill $0$) is champion.

from fractions import Fraction as F
from itertools import permutations
p = F(2, 3)
def gw(x, y):                            # outcomes of one game: (winner, prob)
    return [(x, p if x < y else 1 - p), (y, (1 - p) if x < y else p)]

def four():
    total = F(0)
    for A, B, C, D in permutations(range(4)):       # seat -> skill (0 = best)
        acc = F(0)
        for w1, q1 in gw(A, B):                      # A v B
            for w2, q2 in gw(w1, C):                 # winner v C
                for w3, q3 in gw(w1, D):             # winner v D
                    if w2 == w3:
                        if w2 == 0: acc += q1 * q2 * q3
                    else:
                        for ch, qc in gw(w2, w3):    # title game
                            if ch == 0: acc += q1 * q2 * q3 * qc
        total += acc
    return total / F(24)

def five():
    total = F(0)
    for A, B, C, D, E in permutations(range(5)):
        acc = F(0)
        for a, qa in gw(A, B):                       # G1 winner = a
            for g2, q2 in gw(a, C):                  # G2 a v C
                if g2 == a:                          # a wins -> plays D and E
                    for dw, qd in gw(a, D):
                        for ew, qe in gw(a, E):
                            for ch, qc in gw(dw, ew):
                                if ch == 0: acc += qa * q2 * qd * qe * qc
                else:                                # a loses to C -> a v D
                    for g3, q3 in gw(a, D):
                        if g3 == a:        # a beats D: a v E, then v C
                            for ew, qe in gw(a, E):
                                for ch, qc in gw(ew, C):
                                    if ch == 0: acc += qa * q2 * q3 * qe * qc
                        else:              # a loses D: C v E, then v D
                            for ce, qce in gw(C, E):
                                for ch, qc in gw(ce, D):
                                    if ch == 0: acc += qa * q2 * q3 * qce * qc
        total += acc
    return total / F(120)

print("4 players / 4 games:", four(), "=", float(four()))
print("5 players / 5 games:", five(), "=", float(five()))
# 4 players / 4 games: 38/81 = 0.46913580...
# 5 players / 5 games: 1496/3645 = 0.41042524...

The exact enumeration returns $38/81$ for the four-player schedule and $1496/3645$ for the five-player one, matching the boxed answers.