Picture Frames That Crash To The Floor

Riddler Express

Imagine a framed picture suspended by a cord that hangs on two nails. If the picture were hung normally, you would expect the removal of one nail to leave it hanging on the other. How can you hang a picture on two nails so that if you remove either nail the picture crashes to the floor?

The Riddler, FiveThirtyEight, February 9, 2018(original post)

Solution

The idea. Each time the cord passes a nail, record an $x_i$ if it goes clockwise around nail $i$ and $x_i^{-1}$ if counter-clockwise. Reading along the cord from one end to the other produces a word in the symbols $x_1, x_1^{-1}, x_2, x_2^{-1}, \ldots$. The picture stays up on a given subset $S$ of the nails present if and only if that word is the empty word in the free group generated by $\{x_i : i \in S\}$, i.e. once you erase every $x_j^{\pm 1}$ for $j \notin S$ and cancel adjacent inverses, nothing should remain.

So the Express asks: find a word $w$ in $x_1, x_2$ such that $w \ne 1$ in the free group on $\{x_1, x_2\}$ (so the picture stays up when both nails are present), but $w = 1$ once either generator is set equal to the identity.

The construction. The commutator $$w = x_1 x_2 x_1^{-1} x_2^{-1}$$ does the job. Erase $x_1$ and the word becomes $x_2 x_2^{-1}$, which cancels to the empty word, so removing nail $1$ drops the picture. Erase $x_2$ and the word becomes $x_1 x_1^{-1}$, which again cancels. And $w$ is not the identity in the free group on $\{x_1, x_2\}$ (it is the standard generator of the commutator subgroup), so with both nails in place the cord cannot be pulled free.

The computation

Treat a hanging recipe as a list of pairs $(i, \pm 1)$ read along the cord. Free-group reduction is just a stack: walk the word, push each letter, and pop whenever the top two are mutual inverses. The picture stays up on subset $S$ iff the reduced word over $S$ is empty. Check that the commutator $w = x_1 x_2 x_1^{-1} x_2^{-1}$ reduces to nothing when either generator is removed and survives reduction when both are present.

1. Implement free-group reduction as a one-pass stack.

2. Apply it to $w$ restricted to the surviving generator set.

3. Check $w \ne 1$ on $\{1,2\}$ and $w = 1$ on $\{2\}$ and $\{1\}$.

def reduce(word):
    stack = []
    for g, s in word:
        if stack and stack[-1] == (g, -s):
            stack.pop()
        else:
            stack.append((g, s))
    return stack

def restrict(word, keep):
    return reduce([(g, s) for g, s in word if g in keep])

w = [(1, 1), (2, 1), (1, -1), (2, -1)]            # x1 x2 x1^-1 x2^-1
print('both:   ', restrict(w, {1, 2}))            # nonempty
print('nail 1: ', restrict(w, {2}))               # []
print('nail 2: ', restrict(w, {1}))               # []

The script prints the full word for the “both” case (nontrivial), and [] for both single-nail restrictions: the picture is hanging when both nails are present and falls when either is removed.

Riddler Classic

What about three nails? What about four nails? What about on two red nails and two blue nails such that the picture falls if both red nails are removed and if both blue nails are removed but remains hanging if one of each colour is removed?

The Riddler, FiveThirtyEight, February 9, 2018(original post)

Solution

The pattern. Write $[a, b] = a b a^{-1} b^{-1}$ for the commutator of two words. The Express used $[x_1, x_2]$ to enforce “both nails needed.” Iterating this construction yields a hanging recipe for any number of nails. The key fact: in the free group on $x_1, \ldots, x_n$, the commutator $[u, v]$ is trivial whenever either $u$ or $v$ is trivial, but is nontrivial whenever both $u$ and $v$ are nontrivial. So if $u$ is a hanging recipe for the first $n - 1$ nails (falls when any one of them is removed, survives when all are present), then $[u, x_n] = u x_n u^{-1} x_n^{-1}$ is a hanging recipe for $n$ nails.

Three nails. Start with the Express word $u = [x_1, x_2]$, then form $$[[x_1, x_2], x_3] = u x_3 u^{-1} x_3^{-1} = x_1 x_2 x_1^{-1} x_2^{-1} x_3 x_2 x_1 x_2^{-1} x_1^{-1} x_3^{-1},$$ a word of length $10$. Removing nail $3$ kills the two $x_3$ letters and leaves $u u^{-1} = 1$. Removing nail $1$ leaves $u \to x_2 x_2^{-1} = 1$, so the whole word reduces to $1 \cdot x_3 \cdot 1 \cdot x_3^{-1} = 1$. Same for nail $2$. With all three nails in place, no further cancellation is possible and the word is nontrivial.

Four nails. The same idea, one step deeper. Setting $v = [x_3, x_4]$ in parallel and forming $$[\,[x_1, x_2],\, [x_3, x_4]\,]$$ gives a balanced length-$16$ word. Removing any one of the four nails kills its bracketed factor (turning $u$ or $v$ into $1$), and the outer commutator then collapses to $1$.

Two red, two blue. The red/blue puzzle wants the picture to fall iff both reds are removed or both blues are removed, but to stay up if one of each is removed. Let reds be nails $1, 2$ and blues be nails $3, 4$. Form the commutator of the products $$\begin{aligned} w = [x_1 x_2,\, x_3 x_4] &= x_1 x_2 \cdot x_3 x_4 \cdot (x_1 x_2)^{-1} \cdot (x_3 x_4)^{-1} \\ &= x_1 x_2 x_3 x_4 x_2^{-1} x_1^{-1} x_4^{-1} x_3^{-1}, \end{aligned}$$ a word of length $8$. Removing both reds (kill $x_1$ and $x_2$): the first factor $x_1 x_2$ collapses to $1$, and the commutator $[1, x_3 x_4] = 1$. Same with both blues. Removing one of each: say nails $1$ and $3$ are kept (so $x_2, x_4$ erased). The word becomes $$x_1 x_3 x_1^{-1} x_3^{-1} = [x_1, x_3],$$ the Express commutator on the surviving generators, which is nontrivial. The four “one of each” cases all yield a $[x_i, x_j]$-shaped commutator on the survivors.

The computation

Re-use the free-group reducer of The computation above. For each candidate word, take every subset of generators corresponding to a “nails present” state and reduce; verify the word is empty exactly when the puzzle says the picture should fall.

1. Build the four candidate words (three-nail iterated commutator, four-nail nested commutator, two-red-two-blue commutator).

2. For each, walk over all $2^n$ subsets of the $n$ nails.

3. Check the reduced restriction is empty iff the corresponding subset of nails is removed in the puzzle’s prescription.

def reduce(word):
    stack = []
    for g, s in word:
        if stack and stack[-1] == (g, -s):
            stack.pop()
        else:
            stack.append((g, s))
    return stack

def restrict(word, keep):
    return reduce([(g, s) for g, s in word if g in keep])

def inv(word):
    return [(g, -s) for g, s in reversed(word)]

def commutator(a, b):
    return a + b + inv(a) + inv(b)

x = {i: [(i, 1)] for i in (1, 2, 3, 4)}

# Three nails: [[x1, x2], x3]
w3 = commutator(commutator(x[1], x[2]), x[3])
print('3-nail length', len(w3))
for nails in [{1,2,3}, {2,3}, {1,3}, {1,2}]:
    print('  keep', nails, '->', restrict(w3, nails))

# Four nails: [[x1, x2], [x3, x4]]
w4 = commutator(commutator(x[1], x[2]), commutator(x[3], x[4]))
print('4-nail length', len(w4))
for nails in [{1,2,3,4}, {2,3,4}, {1,3,4}, {1,2,4}, {1,2,3}]:
    print('  keep', nails, '->', len(restrict(w4, nails)))

# Red/blue: [x1 x2, x3 x4], reds = {1,2}, blues = {3,4}
wrb = commutator(x[1] + x[2], x[3] + x[4])
print('red/blue length', len(wrb))
for nails in [{3,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {1,2,3,4}]:
    print('  keep', nails, '->', restrict(wrb, nails))

The script prints, in summary: $w_3$ has length $10$ and reduces to the empty word when any one of nails $1, 2, 3$ is removed; $w_4$ has length $16$ and reduces to the empty word when any one of nails $1, 2, 3, 4$ is removed; $w_{\mathrm{rb}}$ has length $8$ and reduces to the empty word when nails $\{1,2\}$ or $\{3,4\}$ are removed, but stays nontrivial for each of the four “one red, one blue” removals. All three cases match the boxed answer.