Picture-Hanging Puzzles
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...
Main Authors: | Demaine, Erik D, Demaine, Martin L, Minsky, Yair N., Mitchell, Joseph S. B., Rivest, Ronald L, Pǎtraşcu, Mihai |
---|---|
Other Authors: | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
Format: | Article |
Language: | English |
Published: |
Springer Science and Business Media LLC
2020
|
Online Access: | https://hdl.handle.net/1721.1/128234 |
Similar Items
-
Picture-hanging puzzles
by: Demaine, Erik D., et al.
Published: (2012) -
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
by: Bosboom, Jeffrey, et al.
Published: (2021) -
Bust-a-Move/Puzzle Bobble Is NP-complete
by: Langerman, Stefan, et al.
Published: (2017) -
Symmetric assembly puzzles are hard, beyond a few pieces
by: Demaine, Erik D, et al.
Published: (2020) -
A simple proof that the (n2 − 1)-puzzle is hard
by: Demaine, Erik D, et al.
Published: (2021)