To Solve The Eccentric Billionaire’s Puzzle, You Must First Defeat The Banker

Riddler Express

Abby and Beatrix roll two six-sided dice whose faces are coloured red or blue (rather than numbered). Abby wins if the top faces share a colour and Beatrix wins if they do not. One die has five blue sides and one red side. How many red and blue sides must the other die have for the game to be fair?

The Riddler, FiveThirtyEight, September 14, 2018(original post)

Solution

Let the second die have $x$ red sides and $6 - x$ blue sides, with $0 \leq x \leq 6$. Abby wins when both faces are red, or both are blue: $$\Pr(\text{match}) \;=\; \tfrac{1}{6} \cdot \tfrac{x}{6} \;+\; \tfrac{5}{6} \cdot \tfrac{6 - x}{6} \;=\; \frac{x + 5(6 - x)}{36} \;=\; \frac{30 - 4x}{36}.$$ A fair game asks $\Pr(\text{match}) = 1/2 = 18/36$: $$30 - 4x = 18 \quad \Longrightarrow \quad x = 3.$$ $$\boxed{\text{Three red sides and three blue sides.}}$$ The clean reason: a perfectly balanced die’s colour is a fair coin, and it matches the other die exactly half the time regardless of how the other die is painted.

The computation

Brute-force every $x \in \{0, 1, \ldots, 6\}$ and exhaustively enumerate the $36$ rolls.

1. For each $x$ build the two dice as length-$6$ colour lists.

2. Iterate the $6 \times 6$ rolls and tally matches.

3. Print $\Pr(\text{match})$ for each $x$ and identify the fair value.

from fractions import Fraction

die_A = ['B'] * 5 + ['R']

for x in range(7):
    die_B = ['R'] * x + ['B'] * (6 - x)
    matches = sum(1 for a in die_A for b in die_B if a == b)
    p = Fraction(matches, 36)
    flag = "  <-- fair" if p == Fraction(1, 2) else ""
    print(f"x={x}: P(match) = {p} = {float(p):.4f}{flag}")

The script prints $\Pr(\text{match}) = 1/2$ exactly at $x = 3$.

Riddler Classic

An eccentric billionaire has published a map and offered $10 million to anyone who can colour it with three colours so that no two bordering regions share a colour. You believe you have a valid colouring but cannot afford the $10,000 it takes to travel to her island to present it. You ask the bank for a $10,000 loan, but the manager will not lend unless he sees a working solution; and showing him the solution lets him claim the prize himself. How can you convince the bank manager that you have a solution without revealing it? Extra credit: do similar protocols exist for other types of problem?

The Riddler, FiveThirtyEight, September 14, 2018(original post)

Solution

This is the textbook setting for an interactive zero-knowledge proof. Goldreich, Micali and Wigderson presented the same construction in 1986 for exactly this puzzle: graph $3$-colouring (the regions are graph vertices, borders are edges). The protocol is famous because $3$-colouring is NP-complete, so by reduction the protocol extends to every problem in NP. The verifier (the banker) ends convinced that the prover (you) holds a valid colouring, but learns nothing else about the colouring itself.

The protocol. Let the map have $V$ regions and $E$ borders. Take your real colouring with three colours, and on each round:

1. Permute the colour labels. Pick a uniformly random permutation of the three colours and apply it to every region. (Renaming red, blue, yellow to, say, blue, yellow, red gives a different but equally valid colouring.)

2. Commit. Cover each region with an opaque envelope (or hash commitment, or any binding commitment scheme), then show the covered map to the banker.

3. Challenge. The banker chooses one border (an edge between two adjacent regions).

4. Reveal. Open the two envelopes the banker named. The banker checks the colours differ.

5. Otherwise the banker has caught you cheating: stop, no loan.

Repeat the entire round (including the colour-permutation) many times.

Why this works.

Soundness. If you do not actually have a valid colouring, at least one border has matching colours. Each round the banker independently picks a uniformly random border, so each round catches you with probability at least $1/E$. After $k$ honest-banker rounds the probability you fool him is at most $(1 - 1/E)^{k}$. For any tolerance $\varepsilon > 0$, taking $k \geq E \ln(1 / \varepsilon)$ suffices to drive the cheating probability below $\varepsilon$. For a map with say $E = 50$ borders, $300$ rounds drop the cheating probability below $0.25\%$; $700$ rounds drive it below $10^{-6}$.

Zero knowledge. The banker sees, in each round, the colours of one border. Because the labels were freshly permuted, each ordered border reveal is a uniformly random ordered pair of distinct colours from three options, independent of the underlying colouring. Equivalently, the banker could have simulated his own transcript using nothing but coin flips. So the protocol reveals exactly that the colouring works, and nothing about which region holds which colour.

Extra credit. Yes, and dramatically so. Goldreich, Micali and Wigderson (1986, 1991) proved that every language in NP admits a computational zero-knowledge proof, conditional on the existence of secure commitment schemes (in turn implied by the existence of one-way functions). The trick is to reduce the language to $3$-colouring (or any other NP-complete problem) and run the protocol above. So any claim whose validity can be checked by a polynomial-time algorithm can be proven in zero knowledge: solutions to Sudoku, to SAT, to Hamiltonian cycle, to discrete log knowledge for a public key, to "this transaction is valid in a private cryptocurrency", and so on. The whole zero-knowledge SNARK industry now in commercial use rests on this foundation.

The computation

Simulate the protocol literally on a small test map. Use a random graph as the map, attach a known valid $3$-colouring, and run many rounds of the honest protocol; then run a "cheating prover" who supplies an invalid colouring and confirm the catch probability matches the bound.

1. Build a $3$-colourable random planar-like graph; produce one valid colouring and one almost-valid colouring with exactly one bad border.

2. Simulate $k$ rounds where the prover permutes colours and the verifier picks a random border.

3. For the honest prover, confirm the protocol never rejects.

4. For the cheating prover, estimate the catch probability over many trials and compare with $1 - (1 - 1/E)^{k}$.

import random
random.seed(0)

# Triangle prism graph: two triangles 0-1-2 and 3-4-5,
# plus matching edges 0-3, 1-4, 2-5. Six vertices, nine edges.
edges = [(0,1),(1,2),(0,2),(3,4),(4,5),(3,5),
         (0,3),(1,4),(2,5)]
# A valid 3-colouring: vertices coloured so no edge is monochrome.
colouring = {0:0, 1:1, 2:2, 3:1, 4:2, 5:0}
# A cheating colouring: edge (0,1) is monochrome (both 0).
cheat = {0:0, 1:0, 2:2, 3:1, 4:2, 5:0}

def round_play(cmap):
    perm = list(range(3)); random.shuffle(perm)
    permuted = {v: perm[c] for v, c in cmap.items()}
    u, v = random.choice(edges)
    return permuted[u] != permuted[v]  # banker accepts iff different

K = 500
honest_catches = sum(1 for _ in range(K) if not round_play(colouring))
print(f"honest, {K} rounds: caught {honest_catches} times (expect 0)")

TRIALS = 20000
caught = sum(
    1
    for _ in range(TRIALS)
    if any(not round_play(cheat) for _ in range(K))
)
import math
expected_catch = 1 - (1 - 1 / len(edges)) ** K
print(f"cheat,  {K} rounds, {TRIALS} trials: caught {caught}/{TRIALS} "
      f"= {caught/TRIALS:.4f}")
print(f"theory: catch prob over {K} rounds = {expected_catch:.6f}")

The honest prover is never caught (the colouring is valid). The cheating prover is caught on essentially every trial: the bound $1 - (1 - 1/9)^{500}$ exceeds $1 - 10^{-25}$, well past detection.