Picture-hanging puzzles

DOI10.1007/S00224-013-9501-0zbMATH Open1303.68068arXiv1203.3602OpenAlexW3100471971MaRDI QIDQ489745FDOQ489745

Ronald L. Rivest, Erik D. Demaine, Mihai Patrascu, Joseph S. B. Mitchell, Martin L. Demaine, Yair N. Minsky

Publication date: 21 January 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed. This construction makes for some fun mathematical magic performances. More generally, we characterize the possible Boolean functions characterizing when the picture falls in terms of which nails get removed as all monotone Boolean functions. This construction requires an exponential number of twists in the worst case, but exponential complexity is almost always necessary for general functions.

Full work available at URL: https://arxiv.org/abs/1203.3602

Recommendations

• Advice on Hanging Pictures
• Any monotone function is realized by interlocked polygons
• Topological insights from the Chinese rings
• The picture problem for 3-complexes.
• The Mercedes Knot Problem

zbMATH Keywords

magicalgorithmstopologymonotone functionsfree group

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Sorting in \(c \log n\) parallel steps
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Improved sorting networks with O(log N) depth

Cited In (4)

• Eraser morphisms and membership problem in groups and monoids
• Khovanov homology for links in thickened multipunctured disks
• Advice on Hanging Pictures
• Fun problems in geometry and beyond

Uses Software

• OEIS

This page was built for publication: Picture-hanging puzzles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489745)