An all-star team of computer scientists has come up with better ways to remove paintings from museum (or any other) walls). The team includes Luxuriant Flowing Hair Club for Scientists (LFHCfS) member Erik Demaine [pictured here] and RSA Security co-founder Ron Rivest. Their study is:
“Picture-Hanging Puzzles,” Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, and Mihai Patrascu, arXiv:1203.3602v1, March 16, 2012.
“If you hang a picture with string looped around two nails, and then remove one of the nails, the picture still hangs around the other nail. Right? This conclusion is correct if you hang the picture around the two nails in the obvious way shown in Figure 1(a). An intriguing puzzle, originally posed by A. Spivak in 1997 [Spi97], asks for a didderent hanging of the picture with the property that removing either nail causes the picture to fall. Figure 1(b) shows a solution to this puzzle….
“We consider a more general form of the puzzle where we want the removal of certain subsets of nails to fell the picture. We show that any such puzzle has a solution: for any collection of subsets of nails, we can construct a picture hanging that falls when any entire subset of nails gets removed, but remains hanging when every subset still has at least one unremoved nail. This result generalizes picture-hanging puzzles to the maximum extent possible.”
Further figures from the study:
