HackerPapers

arXiv:1203.3602cs.DS

Picture-Hanging Puzzles

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

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
18 pages, 8 figures, 11 puzzles. Journal version of FUN 2012 paper
Journal reference
Theory of Computing Systems, 54(4):531-550, May 2014
DOI
doi:10.1007/s00224-013-9501-0
Subjects
cs.DSData Structures and Algorithms math.GNGeneral Topology math.GRGroup Theory

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jan 2021 to Jan 2021. Found in 1 HN submission from Mar 2012 to Mar 2012. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Any Monotone Boolean Function Can Be Realized by Interlocked Polygons (2010) 1 comment

    • See also: https://arxiv.org/pdf/1203.3602.pdf You can also encode any monotone boolean function by hanging a picture on the wall on N nails (one nail per variable). e.g. a "normal" hanging of a picture on two nails would encode an AND gate (it only falls if both nails are…

      TheNewAndyView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.