@InProceedings{DDMMx12,
author = { Erik D. Demaine and Martin L. Demaine and Yair N. Minsky and Joseph S. B. Mitchell and Ronald L. Rivest
and Mihai P{\u a}trascu },
title = { Picture-Hanging Puzzles },
pages = { 81--93 },
booktitle = { Proceedings of the Sixth International Conference on Fun with Algorithms },
editor = { Evangelos Kranakis and Danny Krizanc and Flaminia Luccio },
publisher = { Springer },
date = { 2012-06 },
OPTyear = { 2012 },
OPTmonth = { June 4--6, },
volume = { 7288 },
series = { Lecture Notes in Computer Science },
eventtitle = { FUN 2012 },
eventdate = { 2012-06-04/2012-06-06 },
venue = { Venice, Italy },
urla = { conference },
urlb = { arXiv },
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.
},
}