Misplaced Rocks and Tangled Wires

The Riddler for December 16, 2016. The Express is the full fixed-point distribution of a random shuffle; the Classic is a tower-climbing identification puzzle solved in just two trips.

Riddler Express

Six labelled rocks fall off a shelf and a janitor returns them in random order. The chance all six land behind their correct labels is $1/6! = 1/720$. What are the chances that exactly five are correct, exactly four, three, two, one, and none?

The Riddler, FiveThirtyEight, December 16, 2016(original post)

Solution

“Exactly $k$ correct” means we pick which $k$ rocks sit in their right spots and then derange the other $6-k$, putting none of them home. Choosing the correct ones is $\binom{6}{k}$ ways, and the number of derangements of $m$ items is $$D_m = m!\sum_{i=0}^{m}\frac{(-1)^i}{i!}, \qquad D_0,\dots,D_6 = 1,0,1,2,9,44,265.$$ So the count with exactly $k$ correct is $\binom{6}{k} D_{6-k}$, and dividing by $720$ gives the probabilities. The striking entry is $k=5$: deranging a single rock is impossible ($D_1 = 0$), since if five rocks are home the sixth must be too. The full distribution, in counts out of $720$: $$\boxed{ \begin{array}{c|ccccccc} k & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\hline \#/720 & 265 & 264 & 135 & 40 & 15 & 0 & 1 \end{array}}$$ The $265/720 \approx 36.8\%$ chance of no rock home is the famous derangement probability, already close to its limit $1/e$.

The computation

Encode $\binom{6}{k} D_{6-k}$ directly and check the seven counts sum to $720$.

from math import comb, factorial
def D(n):                                   # derangements of n items
    return round(factorial(n) * sum((-1)**i / factorial(i) for i in range(n + 1)))
counts = {k: comb(6, k) * D(6 - k) for k in range(7)}
print("counts k=0..6:", [counts[k] for k in range(7)], " sum:", sum(counts.values()))
# counts k=0..6: [265, 264, 135, 40, 15, 0, 1]  sum: 720

Riddler Classic

$N$ wires run from the top of a bell tower to the bottom, hopelessly tangled behind a wall. The top ends are labelled $1$ to $N$; the bottom ends are not. Downstairs you may tie wire ends together in any pairs; upstairs a circuit detector tells you which wires are connected below. Tying and testing are quick, but the stairs are not. What is the fewest trips to the top needed to label every bottom wire?

The Riddler, FiveThirtyEight, December 16, 2016(original post)

Solution

For $N = 1$ there is nothing to do (zero trips), and $N = 2$ is hopeless: the two bottom ends are interchangeable and no tying-and-testing can break the symmetry. For every $N > 2$, though, $$\boxed{2 \text{ trips}}$$ suffice, and the trick is to make each wire’s pattern of connections across the two trips act as a unique fingerprint.

Give the bottom ends your own names $B_1, \dots, B_N$. Trip 1: tie $B_1$–$B_2$, $B_3$–$B_4$, and so on, leaving the last one end loose if $N$ is odd and the last two loose if $N$ is even; climb up and record which top labels are paired. Trip 2: untie everything and re-pair shifted by one, $B_N$–$B_1$, $B_2$–$B_3$, $B_4$–$B_5$, …, leaving $B_{N-1}$ loose (odd) or $B_{N-1}, B_{N-2}$ loose (even); climb again and record.

Now read off the chain. One top wire is loose on trip 1 but paired on trip 2: that is $B_N$. Its trip-2 partner must be $B_1$; $B_1$’s trip-1 partner is $B_2$; $B_2$’s trip-2 partner is $B_3$; and so on, alternating between the two logs, each step naming the next bottom wire until all $N$ are pinned down. The asymmetric “leave loose” rule is what plants a unique starting anchor so the chain never stalls or doubles back.

The computation

Encode the strategy and test that it genuinely determines every wire: build a hidden top-to-bottom correspondence, run the two pairings, and count how many correspondences are consistent with the observed connections. For $N > 2$ the answer must be exactly one.

import itertools, random
def trip1_pairs(N):                          # B1-B2, B3-B4, ... leave last 1 (odd) / 2 (even)
    usable = N - (1 if N % 2 else 2)
    return [(i, i + 1) for i in range(1, usable, 2)]
def trip2_pairs(N):                          # BN-B1, B2-B3, ... leave B(N-1) (odd) / B(N-1),B(N-2)
    seq = [N] + list(range(1, N - 1)) if N % 2 else [N] + list(range(1, N - 2))
    return [(seq[k], seq[k + 1]) for k in range(0, len(seq) - 1, 2)]

def consistent(N, seed):
    rng = random.Random(seed); perm = list(range(1, N + 1)); rng.shuffle(perm)
    top = {perm[t - 1]: t for t in range(1, N + 1)}            # bottom label -> top (hidden truth)
    obs = lambda pr: frozenset(frozenset((top[a], top[b])) for a, b in pr)
    p1, p2 = trip1_pairs(N), trip2_pairs(N); seen = (obs(p1), obs(p2))
    count = 0
    for pm in itertools.permutations(range(1, N + 1)):
        t = {pm[i - 1]: i for i in range(1, N + 1)}
        o = (frozenset(frozenset((t[a], t[b])) for a, b in p1),
             frozenset(frozenset((t[a], t[b])) for a, b in p2))
        count += (o == seen)
    return count
for N in range(1, 9):
    amb = max(consistent(N, s) for s in range(6))
    print(f"N={N}: 2 trips -> {amb} correspondence(s) consistent",
          "(1 = solved)" if amb == 1 else ("(N=2 impossible)" if N == 2 else ""))
# N=1: 1   N=2: 2 (impossible)   N=3..8: all 1 (uniquely solved)