You have two nails in the wall and a painting with a string on its back, which can easily be rested on the nails to hang the painting. If you remove one nail, the painting will still hang on the other. But mathematicians said, “We can make it worse.” In 1997 A. Spivak posed the following riddle: Is there a way to hang the painting so that removing either nail will cause the painting to fall? Since then, mathematicians have expanded this concept into an intriguing family of picture-hanging problems.
Retired computer scientist Tom Verhoeff first explored such problems in a workshop for a grade school math camp, where the campers investigated with actual string and carabiners but also translated the problem into symbols.
On supporting science journalism
If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
In 2012 mathematicians posted a preprint proving that solutions exist for any k-out-of-n picture-hanging problem, where n is the number of nails and removing any k of the nails, but no fewer, will cause the painting to fall. Known solutions, however, can involve very elaborate string wrappings. At the workshop Verhoeff and the participants tackled the 2-out-of-4 problem, in which a painting will fall if any two of four nails are removed. They reduced the length of the shortest known solution from 80 to 58 wraps around the nails.
Later, Verhoeff worked it all the way down to 18—and, with the help of then Ph.D. student Jens Heuseveldt and a computer program to check all smaller hangings, down to the absolute minimum of 16. Initially Verhoeff showed Heuseveldt a computer program to solve the problem in about two hours. “I then told him my program could solve it in two seconds,” Heuseveldt says. “And now his program is even faster than mine.” Verhoeff posted the results along with the shortest known explicit solutions for large families of these problems to the preprint server arXiv.org.
Why are mathematicians so interested in hanging paintings in complex and terrible ways? Although the problem’s framing might sound silly, the underlying mechanics have deep connections to group theory, knot theory, graph theory, and other areas of mathematics. In the 1-out-of-n case, for example, solutions can be described as loops drawn on the edges of an n-dimensional cube that pass through every corner. Plus, it’s possible to find hangings for any “reasonable” set of rules for paintings to fall—for example, you can’t require that removing just nail A makes the painting fall but removing A and B leaves it hanging. These rules exactly correspond to the monotone Boolean functions—a function type crucial in fields such as cryptography and voting theory.
But asking whether the problem is useful is the wrong question, Verhoeff argues. “For humanity as a whole, we don’t know where our spaceship is going and what we will need to survive,” he says, “and play is one of the ways in which we learn.”
Subscribe to Support Independent Journalism
Great science journalism requires human expertise, time, effort and creativity. And it costs money. That’s why I and the journalists here at Scientific American hope you’ll join our community.
When you subscribe, you are supporting staff and freelance journalists who are passionate about telling science stories that are true, important and compelling. Our editors and reporters are often experts in their fields, which means they understand the nuances of big discoveries and can untangle the breakthroughs from the hype. With a subscription, you are also supporting rigorous fact-checking to ensure the words we publish are precise and accurate. And you’re supporting original illustrations, graphics and photos that bring you closer to an advanced laboratory, an ice sheet in Antarctica or a space mission in orbit. You’re helping us craft other types of high-quality journalism as well: Our newsletters are carefully written, edited and curated by staffers you have or will come to know and love. Our Science Quickly podcast is based on original reporting, collaboration with editors and scientists and exacting production.
Subscriptions keep this engine running so we can continue to deliver thoughtful, rigorous and independent science journalism to you. In an era of viral misinformation, this work is crucial. If you value what we do, I hope you’ll consider joining us as a subscriber
