Organize Some Debates! Maximize The Shade!

Riddler Express

Twenty candidates are split for each debate into two panels of ten. Candidates can only criticise others on the same panel. What is the minimum number of rounds (each round splitting the twenty into two panels of ten) so that every candidate shares a stage with every other candidate at least once?

The Riddler, FiveThirtyEight, August 9, 2019(original post)

Solution

In one round a candidate shares the stage with the nine others on their panel, so each round lets a candidate meet at most nine new people. Each candidate must meet all nineteen others, and $$\left\lceil \tfrac{19}{9} \right\rceil = 3,$$ so at least three rounds are needed. Two rounds can never suffice: nine plus nine is eighteen, one short of nineteen.

Three rounds are enough, and the clean way to see it is to break the twenty into four blocks of five, say $W, X, Y, Z$, that always move as units. A panel is then a pair of blocks. Choose the three pairings so that each round the four blocks are matched as a round-robin: $WX{\mid}YZ$, then $WY{\mid}XZ$, then $WZ{\mid}XY$. Over the three rounds every block shares a panel with each of the other three blocks once, so every candidate meets the fifteen people in the other three blocks, plus the four in their own block (with whom they share every panel). That covers all nineteen. $$\boxed{3 \text{ rounds}}$$

The computation

Encode the official three-round schedule and check that the pairs sharing a panel, summed over the three rounds, cover all $\binom{20}{2} = 190$ pairs. Pair the lower bound (each candidate meets at most nine per round) with this construction.

from itertools import combinations
N = 20
def covered(rounds):                 # each round = the set of one 10-panel
    seen = set()
    for panel in rounds:
        other = set(range(1, N + 1)) - panel
        for grp in (panel, other):
            seen.update(combinations(sorted(grp), 2))
    return len(seen) == len(list(combinations(range(1, N + 1), 2)))

r1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
r2 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
r3 = {1, 3, 5, 7, 9, 12, 14, 16, 18, 20}
print("three rounds cover all 190 pairs:", covered([r1, r2, r3]))
print("lower bound (meet <=9 per round):", -(-19 // 9), "rounds")
# three rounds cover all 190 pairs: True
# lower bound (meet <=9 per round): 3 rounds

The three-round schedule covers every pair, and no two-round schedule can, so the minimum is three.

Riddler Classic

You own a circular pond of radius $1$ yard and a collection of thin boards each exactly $1$ yard long. Placing boards one at a time, with each board’s ends resting on the bank or on a previously placed board, how many boards are needed to cover the centre point of the pond?

The Riddler, FiveThirtyEight, August 9, 2019(original post)

Status

The answer is $12$ boards, but reaching it is a delicate geometric construction rather than a derivable computation. The winning arrangement (due to solver Tim Black, found with help from a computer search) builds a sparse scaffold inward from the bank, just dense enough to reach the centre while spending as few boards as possible; the standard way in is to work backwards from the board that finally covers the centre. That $11$ boards are not enough was shown only by extensive search and a near-miss symmetric attempt (Zach Wissner-Gross), not by a clean argument.

Because the result rests on a hand-built, image-specified construction and a search-based lower bound rather than a self-contained derivation, the Classic is deferred from the worked-solution standard, in the same category as the other geometric construction puzzles whose answers come from figures and search.