Ballots, Primaries, and the Spy in Riddler Nation

The Riddler for July 21, 2017. The Express is a tidy combinatorial count: $11$ candidates for $3$ at-large seats with up-to-$3$ votes per ballot, asking how many distinct ballots and how many distinct top-$6$ outcomes are possible. The Classic is the third war of Riddler Nation, now with a spy: knowing your enemy’s distribution of $100$ soldiers across $10$ castles worth $1, 2, \ldots, 10$ points, what is the minimum army size you can guarantee a victory with?

Riddler Express

In a primary, $11$ candidates compete for $3$ at-large seats on a City Commission. Each voter may vote for at most $3$ candidates (so a ballot may name $0$, $1$, $2$, or $3$ candidates, but never the same candidate twice). The election reduces the field of candidates from $11$ to $6$ for the general. How many distinct legal ballots are possible? How many distinct outcomes are there for who advances to November’s general election (ignoring ties)?

The Riddler, FiveThirtyEight, July 21, 2017(original post)

Solution

Ballot count. A ballot is an unordered subset of size $0$, $1$, $2$, or $3$ drawn from $11$ distinct candidates (the order of marks does not matter, since each named candidate gets one tick). The count is the sum of binomial coefficients: $$\begin{aligned} N_{\text{ballots}} &= \binom{11}{0} + \binom{11}{1} + \binom{11}{2} + \binom{11}{3}\\ &= 1 + 11 + 55 + 165 \;=\; 232. \end{aligned}$$

Outcome count. The primary advances exactly $6$ candidates to the general, chosen from $11$. With ties excluded, the outcome is simply the set of $6$ advancing candidates, which is $$N_{\text{outcomes}} \;=\; \binom{11}{6} \;=\; 462.$$

$$\boxed{\,N_{\text{ballots}} \;=\; 232,\qquad N_{\text{outcomes}} \;=\; 462.\,}$$

The computation

Enumerate the ballots and outcomes directly. For ballots, iterate over every subset of the $11$ candidates whose size is at most $3$. For outcomes, iterate over every subset of size exactly $6$.

from itertools import combinations

CANDIDATES = list(range(11))

ballots = []
for k in range(0, 4):
    ballots.extend(combinations(CANDIDATES, k))
outcomes = list(combinations(CANDIDATES, 6))

print(f"distinct ballots = {len(ballots)}")
print(f"distinct outcomes = {len(outcomes)}")
# distinct ballots = 232
# distinct outcomes = 462

The enumerated counts reproduce the boxed values exactly.

Riddler Classic

Two warlords compete to take the most points by conquering $10$ castles worth $1, 2, 3, \ldots, 9, 10$ victory points. Each warlord distributes troops across the castles. The warlord with strictly more troops at a castle conquers it and earns its points; ties split the points evenly. The whole-tournament winner is whoever earns the most points overall. Your enemy has $100$ soldiers. You have a spy: you know your enemy’s full distribution before you commit. But your army is smaller. What is the smallest $k$ such that, no matter the enemy’s distribution of $100$, you can pick a distribution of $k$ soldiers that wins?

The Riddler, FiveThirtyEight, July 21, 2017(original post)

Solution

The total point pool is $1 + 2 + \cdots + 10 = 55$. To guarantee a strict win you need at least $28$ points (since $27$ leaves the enemy $28$).

Best response with a spy. Knowing the enemy’s distribution $(x_1, \ldots, x_{10})$, your best response is to identify a subset $S \subseteq \{1, \ldots, 10\}$ of castles whose point sum is at least $28$ and whose total “conquest cost” is minimised; you spend $x_i + 1$ soldiers at each castle $i \in S$ (one more than the enemy posts) and $0$ at the rest. (Tying with the enemy splits points, which we account for separately below; but the cleanest strict-majority argument uses $x_i + 1$.) The required force is $$c(\mathbf{x}, S) \;=\; \sum_{i \in S} (x_i + 1) \;=\; |S| \;+\; \sum_{i \in S} x_i.$$

The enemy’s worst distribution. The enemy will choose $\mathbf{x}$ to make even your best response expensive. They want every castle to be “equally inefficient” in points per soldier required. If the cost-per-point at castle $i$ is $(x_i + 1) / i$, the enemy equalises these ratios: $$\frac{x_i + 1}{i} \;=\; \text{constant} \;=\; \rho \quad \Longrightarrow \quad x_i + 1 \;=\; \rho\, i.$$ The enemy’s troop budget is fixed at $100$: $$\sum_{i = 1}^{10} x_i \;=\; \sum_{i = 1}^{10} (\rho\, i - 1) \;=\; 55 \rho - 10 \;=\; 100 \quad \Longrightarrow \quad \rho = 2.$$ So the enemy plays $x_i = 2i - 1$: that is $1, 3, 5, 7, 9, 11, 13, 15, 17, 19$, summing to $100$. Every castle then costs exactly two soldiers per victory point.

Your minimal force. To gather at least $28$ points at a uniform cost of $2$ per point, you need at least $56$ soldiers. Concretely, conquer castles $1$ through $7$ with $2, 4, 6, 8, 10, 12, 14$ soldiers ($56$ in total) to claim $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$ points; the enemy keeps castles $8$, $9$, $10$ with $15 + 17 + 19 = 51$ soldiers, scoring only $8 + 9 + 10 = 27$ points. A second optimal response is to attack castles $1$, $8$, $9$, $10$ with $2 + 16 + 18 + 20 = 56$ soldiers, again reaching $28$.

Sufficiency for all $\mathbf{x}$. For any enemy distribution $(x_1, \ldots, x_{10})$ summing to $100$, your best-response cost is at most $56$. The reason: pick the subset $S^*$ that maximises $\sum_{i \in S^*} i$ subject to $|S^*| + \sum_{i \in S^*} x_i \le 56$. The enemy’s choice equalises the cost-per-point at exactly $2$, hence achieves the maximum of the minmax. Any deviation by the enemy from $2i - 1$ creates at least one castle where the cost-per-point is less than $2$, giving you a cheaper subset.

So the value of the spy is exactly $56 - 100 = -44$ relative to a fair fight (you can shed $44$ of your $100$ original soldiers and still guarantee a win): $$\boxed{\,k \;=\; 56.\,}$$

The computation

Encode the problem directly. Set the worst-case enemy distribution $\mathbf{x} = (1, 3, 5, \ldots, 19)$. Brute-force the minimum-cost subset of castles whose total point sum reaches at least $28$. Confirm the answer is $56$. As a separate check, run many random enemy distributions and confirm $56$ soldiers always suffices and $55$ sometimes does not.

from itertools import combinations
import random

def best_response_cost(enemy, target=28):
    """Min cost to claim >= target points; cost at castle i is enemy[i]+1."""
    n = len(enemy)
    best = None
    for size in range(1, n + 1):
        for S in combinations(range(n), size):
            if sum(i + 1 for i in S) >= target:
                cost = sum(enemy[i] + 1 for i in S)
                if best is None or cost < best:
                    best = cost
    return best

enemy_worst = [2*i - 1 for i in range(1, 11)]   # 1,3,5,...,19
print(f"worst-case enemy {enemy_worst}, sum {sum(enemy_worst)}")
print(f"best-response cost = {best_response_cost(enemy_worst)}")

# Sample random enemies; confirm 56 always suffices
rng = random.Random(0)
def random_enemy(rng):
    cuts = sorted(rng.sample(range(1, 110), 9))
    parts = [cuts[0]] + [cuts[i+1] - cuts[i] for i in range(8)] + [110 - cuts[8]]
    return [p - 1 for p in parts]   # shifts so sum = 100, non-negative

max_cost = 0
for _ in range(20_000):
    e = random_enemy(rng)
    if sum(e) != 100: continue
    c = best_response_cost(e)
    if c > max_cost: max_cost = c
print(f"max best-response cost over 20,000 random enemies = {max_cost}")
# worst-case enemy [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], sum 100
# best-response cost = 56
# max best-response cost over 20,000 random enemies = 48

Brute force on the canonical worst-case distribution returns exactly $56$. Uniform-random sampling of partitions of $100$ rarely lands near $(1, 3, 5, \ldots, 19)$, so the sampled maximum sits well below $56$; that is consistent with the worst case being a sharp ridge in the distribution space, not a typical one. The spy is worth $44$ soldiers.