Mathematics
The Picture-Hanging Puzzle
- Free groups
- Topology
- Puzzles
In simple words
Hang a picture on two nails and pull one out. It still hangs on the other one. That is what the second nail is for.
But what if you wanted the opposite? Could you wind the string so cleverly that pulling out any one nail, whichever you pick, brings the whole picture down? With two nails? With three, or a hundred? It sounds impossible. It isn't, and the trick hides inside a beautiful piece of mathematics.
A puzzle from a magazine
The puzzle appeared in 1997 as a brainteaser by A. Spivak in Quantum magazine, under the title Strange painting [1]. Michael Hardy of Harvard later posed it to Marilyn vos Savant, whose column printed the puzzle and its solution in June 2001 [2]. Torsten Sillke passed it around the puzzle community, together with an observation of Werner Schwärzler that the Borromean rings already solve it [3], and on Ed Pegg's MathPuzzle.com Neil Fitzgerald connected it with group theory and Chris Lusby Taylor found a far more efficient solution in 2002 [4]. In 2012 Erik Demaine and five co-authors turned the puzzle into a theory [5]. They showed that for any collection of groups of nails there is a hanging that falls exactly when one whole group is pulled out, though such general rules can need an exponentially long rope. Erik Demaine also performs the solutions as magic tricks, with rope wound around the arms of volunteers from the audience, and on one occasion, having forgotten his rope, with a fire hose borrowed from the local fire department [5].
Ropes are words
As with the Rubik's cube, the way in is a group. The wall with nails is a plane with points removed. A rope that starts at one corner of the picture and ends at the other can be slid around freely, as long as it does not pass through a nail, and what cannot be undone by sliding is recorded by the fundamental group of the punctured plane. That group is the free group on generators [6]. Write for one clockwise loop around the first nail and for one anticlockwise loop, and similarly and so on. The rope becomes a word, read from left to right. The only rule is that a letter next to its inverse cancels, , and every word cancels down to a unique reduced word. The picture stays up when the reduced word is not empty, and it falls when everything cancels [5].
Pulling out a nail erases all of its letters, which is the homomorphism that sends that generator to the identity. The puzzle therefore asks for a word that does not reduce to the empty word, but that does as soon as the letters of any one nail are deleted. For two nails the commutator does it,
Nothing cancels, so the picture hangs. Without nail A the word is , and without nail B it is . This is the Borromean rings in disguise: stretch two of the three rings into straight lines, which play the nails, and the third ring hangs on them in exactly this way [5]. More nails correspond to Brunnian links, rings that hold together as a whole but fall apart when any one is cut, which Hermann Brunn constructed in 1892 [7].
Doubling: the iterated commutator
The commutator has a property that makes it the right tool. If either of its two parts collapses to the empty word, the whole commutator collapses too, since and . Fitzgerald's solution nests it [5],
so that . Pulling out any of the first nails collapses , and pulling out the last one leaves . With all nails in, the word does not cancel, because in a free group two elements commute only when they are powers of a common element, which and are not. The price is length. Every step doubles the word and adds two letters, so has letters, and the first two nails each carry loops: 128 of them for eight nails.
Halving: the balanced word
Lusby Taylor's idea is to split the nails in two halves instead of peeling them off one at a time [4][5]. With the word for nails to ,
The same argument shows that it works: pulling out any nail collapses one of the two halves, and with it the whole word. But now the length only doubles when the number of nails doubles, so for a power of two the word has exactly letters and every nail is used exactly times. In general, with and , the length is , never more than [5][8].
| Nails n | Iterated commutator | Balanced word |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 4 | 4 |
| 3 | 10 | 10 |
| 4 | 22 | 16 |
| 5 | 46 | 28 |
| 6 | 94 | 40 |
| 7 | 190 | 52 |
| 8 | 382 | 64 |
It cannot be done much better. Gartside and Greenwood proved in 2007 that every solution needs a number of letters growing like [9], and the authors of the puzzle paper note that their bound matches the balanced construction exactly [10]. For three nails a direct search confirms it: none of the 2,929,686 reduced words with fewer than ten letters works, while 240 words of exactly ten letters do. One loophole remains. If the rope may also wind around itself, not just around the nails, Michael Paterson found a solution that needs only a number of crossings proportional to [5].
Inside the code
Both constructions are a few lines once the commutator is in place. The balanced one recurses on the two halves:
// The commutator [u, v] = u v u⁻¹ v⁻¹ collapses as soon as u or v does.
const commutator = (u, v) => [...u, ...v, ...invWord(u), ...invWord(v)];
// The balanced word: the commutator of the words for the two halves of the nails.
function balanced(n) {
const E = (i, j) => {
if (i === j) return [letter(i)];
const m = Math.floor((i + j) / 2);
return commutator(E(i, m), E(m + 1, j));
};
return E(0, n - 1);
}Pulling a nail deletes its letters, and the fall is animated by free reduction, one cancellation per step. A stack does it in a single pass, and every intermediate word is kept for the animation:
// Free reduction with a stack: a letter that undoes the top of the stack
// cancels it, any other letter is pushed. What remains is the reduced word.
for (let k = 0; k < rest.length; k++) {
const c = rest[k];
if (stack.length && stack[stack.length - 1] === inv(c)) {
stack.pop();
words.push([...stack, ...rest.slice(k + 1)]); // one step of the animation
} else stack.push(c);
}The drawing is built so that it realizes the word exactly. Each letter is an arch over its nail, and everything between the arches runs below the nails, a region without holes, where the rope can be rearranged freely. To make sure the picture tells the truth, the tests read the word back from the drawn rope, by the standard trick of cutting the wall along a vertical ray above each nail, and compare it with the word that was meant:
// Reading the drawing back as a word: follow the rope and note each time it
// crosses the vertical ray above a nail, rightwards as X and leftwards as x.
for (let k = 0; k + 1 < pts.length; k++) {
const [x0, y0] = pts[k], [x1, y1] = pts[k + 1];
for (const nail of nails) {
if ((x0 < nail.x) === (x1 < nail.x)) continue;
const y = y0 + ((nail.x - x0) / (x1 - x0)) * (y1 - y0);
if (y < nail.y) out.push(x1 > x0 ? letter(nail.i) : letter(nail.i).toLowerCase());
}
}Try it yourself
Start with two nails, press Reset and then Step to lay the rope letter by letter, then pull out either nail and watch the word cancel and the picture drop. With three nails both constructions give the same ten letters. Go to four nails and switch the construction: the iterated word has 22 letters, the balanced one 16. At eight nails the difference is dramatic, 382 letters against 64, with 128 loops crowded around each of nails A and B in the iterated word and exactly eight around every nail in the balanced one. Whichever nail you pull out, the word panel shows each cancellation before the picture falls, and Put the nail back hangs it up again.
References
- [1] A. Spivak, Brainteasers B 201: Strange painting, Quantum, p. 13 (May/June 1997), solution p. 60.
- [2] M. vos Savant, Ask Marilyn, Parade (June 10 and June 17, 2001).
- [3] T. Sillke, Strange painting (2001), puzzle page.
- [4] E. Pegg Jr., Picture hanging, MathPuzzle.com (2002).
- [5] E. D. Demaine, M. L. Demaine, Y. N. Minsky, J. S. B. Mitchell, R. L. Rivest, and M. Pătraşcu, Picture-hanging puzzles, Theory Comput. Syst. 54, 531 (2014).
- [6] A. Hatcher, Algebraic Topology (Cambridge University Press, Cambridge, 2002).
- [7] H. Brunn, Über Verkettung, Sitzungsber. Bayer. Akad. Wiss. Math.-Naturwiss. Abt. 22, 77 (1892).
- [8] K. Ellul, B. Krawetz, J. Shallit, and M.-w. Wang, Regular expressions: new results and open problems, J. Autom. Lang. Comb. 9, 233 (2005).
- [9] P. Gartside and S. Greenwood, Brunnian links, Fund. Math. 193, 259 (2007).
- [10] E. D. Demaine et al., Picture-hanging puzzles, paper page with the authors’ update on the shortest solutions.