Picture-Hanging Puzzles | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

Picture-Hanging Puzzles

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. This construction also turns out to be essentially the same as the solution that comes out of the Brunnian-link construction described in Sect. 3.1.

References

  1. Ajtai, M., Komlós, J., Szemerédi, E.: Sorting in clogn parallel steps. Combinatorica 3(1), 1–19 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  2. Brunn, H.: Über Verkettung. In: Sitzungsbericht der Bayerischen Akademie der Wissenschaft Mathematisch Naturwissenschaftliche Abteilung, vol. 22, pp. 77–99 (1892)

    Google Scholar 

  3. Demaine, E.D., Demaine, M.L., Uehara, R.: Any monotone Boolean function can be realized by interlocked polygons. In: Proceedings of the 22nd Canadian Conference on Computational Geometry, Winnipeg, Canada, August 2010, pp. 139–142 (2010)

    Google Scholar 

  4. Ellul, K., Krawetz, B., Shallit, J., Wang, M.-w.: Regular expressions: new results and open problems. J. Autom. Lang. Comb. 9(2–3), 233–256 (2005)

    MathSciNet  Google Scholar 

  5. Makanin, G.S.: Decidability of the universal and positive theories of a free group. Math. USSR, Izv. 25(1), 75–88 (1985). Translated from Russian edition, 48(4) (1984)

    Article  MATH  MathSciNet  Google Scholar 

  6. Paterson, M.S.: Improved sorting networks with O(logN) depth. Algorithmica 5, 75–92 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  7. Pegg Jr., Ed: Picture Hanging (2002). http://www.mathpuzzle.com/hangingpicture.htm

    Google Scholar 

  8. Rolfsen, D.: Knots and Links. Publish or Perish, Houston (1976)

    MATH  Google Scholar 

  9. Sillke, T.: Strange painting (2001). http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/quantum/B201

    Google Scholar 

  10. Sloane, N.J.A.: Sequence A073121. In: On-Line Encyclopedia of Integer Sequences (2002). http://www.research.att.com/projects/OEIS?Anum=A073121

    Google Scholar 

  11. Spivak, A.: Brainteasers B 201: Strange painting. Quantum, page 13 (1997). Solution on page 60, figure 5

  12. Theodore, S.: Brunnian braids and some of their generalizations. (1999). http://arXiv.org/abs/math/9907072. To appear in Bulletin of the London Mathematical Society

    Google Scholar 

  13. Tait, P.G.: On knots. Trans. R. Soc. Edinb. 28, 145–190 (1876)

    Google Scholar 

  14. vos Savant, M., Marilyn, A.: PARADE (2001). Puzzle posed in June 10 issue and solved in June 17 issue

Download references

Acknowledgements

We thank Jason Cantarella for helpful early discussions, Kim Whittlesey for pointing out reference [12], and the anonymous referees for helpful comments.

Author information

Authors and Affiliations

  1. MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., Cambridge, MA, 02139, USA

    Erik D. Demaine, Martin L. Demaine & Ronald L. Rivest

  2. Department of Mathematics, Yale University, 10 Hillhouse Ave., New Haven, CT, 06520, USA

    Yair N. Minsky

  3. Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY, 11794-3600, USA

    Joseph S. B. Mitchell

  4. AT&T Labs—Research, 180 Park Ave., Florham Park, NJ, 07932, USA

    Mihai Pǎtraşcu

Authors
  1. Erik D. Demaine
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin L. Demaine
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yair N. Minsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Joseph S. B. Mitchell
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ronald L. Rivest
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Mihai Pǎtraşcu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Erik D. Demaine.

Additional information

A preliminary version of this paper appeared in Proceedings of the 6th International Conference on Fun with Algorithms, Venice, 2012.

J.S.B. Mitchell was partially supported by NSF grant CCF-1018388.

Appendix: Puzzle Solutions

Appendix: Puzzle Solutions

This appendix gives solutions to the puzzles from Sect. 2 in the free-group notation defined in Sect. 3.2. These solutions are based on the basic theory described in Sect. 3, though they do not all fall under the specific statement of Theorem 2. The solutions are not unique; shorter solutions may well exist.

Puzzle 1

Figure 6 shows \(S_{3} = x_{1} x_{2} x_{3} x_{2}^{-1} x_{3}^{-1} x_{1}^{-1} x_{3} x_{2} x_{3}^{-1} x_{2}^{-1}\).

Puzzle 2

\(x_{1} x_{2} x_{3} x_{1}^{-1} x_{2}^{-1} x_{3}^{-1}\).

Puzzle 3

\([x_{1}, x_{2} x_{3}] = x_{1} x_{2} x_{3} x_{1}^{-1} x_{3}^{-1} x_{2}^{-1}\), where the nails are ordered from left to right.

Puzzle 4

\(E(1:4) = x_{1} x_{2} x_{1}^{-1} x_{2}^{-1} x_{3} x_{4} x_{3}^{-1} x_{4}^{-1} x_{2} x_{1} x_{2}^{-1} x_{1}^{-1} x_{4} x_{3} x_{4}^{-1} x_{3}^{-1}\).

Puzzle 5

\([[x_{1} x_{2}, [x_{1} x_{3}, x_{1} x_{4}]], [x_{2} x_{3}, [x_{2} x_{4}, x_{3} x_{4}]]] = x_{1} x_{2} x_{1} x_{3} x_{1} x_{4} x_{3}^{-1} x_{1}^{-1} x_{4}^{-1} x_{1}^{-1} x_{2}^{-1} x_{1}^{-1} x_{1} x_{4} x_{1} x_{3} x_{4}^{-1} x_{1}^{-1} x_{3}^{-1} x_{1}^{-1} x_{2} x_{3} x_{2} x_{4} x_{3} x_{4} x_{4}^{-1} x_{2}^{-1} x_{4}^{-1} x_{3}^{-1} x_{3}^{-1} x_{2}^{-1} x_{3} x_{4} x_{2} x_{4} x_{4}^{-1} x_{3}^{-1} x_{4}^{-1} x_{2}^{-1} x_{1} x_{3} x_{1} x_{4} x_{3}^{-1} x_{1}^{-1} x_{4}^{-1} x_{1}^{-1} x_{1} x_{2} x_{1} x_{4} x_{1} x_{3} x_{4}^{-1} x_{1}^{-1} x_{3}^{-1} x_{1}^{-1} x_{2}^{-1} x_{1}^{-1} x_{2} x_{4}x_{3} x_{4} x_{4}^{-1} x_{2}^{-1} x_{4}^{-1} x_{3}^{-1} x_{2} x_{3} x_{3} x_{4} x_{2} x_{4} x_{4}^{-1} x_{3}^{-1} x_{4}^{-1} x_{2}^{-1} x_{3}^{-1} x_{2}^{-1}\).

Puzzle 6

\(x_{1} x_{2} x_{3} x_{4} x_{1}^{-1} x_{2}^{-1} x_{3}^{-1} x_{4}^{-1}\).

Puzzle 7

\([x_{1} x_{2}, x_{3} x_{4}] = x_{1} x_{2} x_{3} x_{4} x_{2}^{-1} x_{1}^{-1} x_{4}^{-1} x_{3}^{-1}\), where x 1 and x 2 are red and x 3 and x 4 are blue.

Puzzle 8

\([S_{2}, x_{3} x_{4}] = x_{1} x_{2} x_{1}^{-1} x_{2}^{-1} x_{3} x_{4} x_{2} x_{1} x_{2}^{-1} x_{1}^{-1} x_{4}^{-1} x_{3}^{-1}\), where x 1 and x 2 are red and x 3 and x 4 are blue.

Puzzle 9

\([S_{3}, x_{4} x_{5} x_{6}] = x_{1} x_{2} x_{3} x_{2}^{-1} x_{3}^{-1} x_{1}^{-1} x_{3} x_{2} x_{3}^{-1} x_{2}^{-1} x_{4} x_{5} x_{6} x_{2} x_{3} x_{2}^{-1} x_{3}^{-1} x_{1} x_{3} x_{2} x_{3}^{-1} x_{2}^{-1} x_{1}^{-1} x_{6}^{-1} x_{5}^{-1} x_{4}^{-1}\), where x 1, x 2, and x 3 are red and x 4, x 5, and x 6 are blue.

Puzzle 10

\([S_{3}, x_{4} x_{5} x_{6} x_{4}^{-1} x_{5}^{-1} x_{6}^{-1}] = x_{1} x_{2} x_{3} x_{2}^{-1} x_{3}^{-1} x_{1}^{-1} x_{3} x_{2} x_{3}^{-1} x_{2}^{-1} x_{4} x_{5} x_{6} x_{4}^{-1} x_{5}^{-1} x_{6}^{-1} x_{2} x_{3} x_{2}^{-1} x_{3}^{-1} x_{1} x_{3} x_{2} x_{3}^{-1} x_{2}^{-1} x_{1}^{-1} x_{6} x_{5} x_{4} x_{6}^{-1} x_{5}^{-1} x_{4}^{-1}\), where x 1, x 2, and x 3 are red and x 4, x 5, and x 6 are blue.

Puzzle 11

\([[[x_{1}x_{3}, [x_{2}x_{4}, x_{1}x_{5}]], [x_{3}x_{6}, [x_{1}x_{4}, x_{2}x_{3}]]], [[x_{1}x_{6}, [x_{2}x_{5}, x_{4}x_{6}]], [x_{3}x_{5}, [x_{2}x_{6}, x_{4}x_{5}]]]] = x_{1} x_{3} x_{2} x_{4} x_{1} x_{5} x_{4}^{-1} x_{2}^{-1} x_{5}^{-1} x_{1}^{-1} x_{3}^{-1} x_{1}^{-1} x_{1} x_{5} x_{2} x_{4} x_{5}^{-1} x_{1}^{-1} x_{4}^{-1} x_{2}^{-1} x_{3} x_{6} x_{1} x_{4} x_{2} x_{3} x_{4}^{-1} x_{1}^{-1} x_{3}^{-1} x_{2}^{-1} x_{6}^{-1} x_{3}^{-1} x_{2} x_{3} x_{1} x_{4} x_{3}^{-1} x_{2}^{-1} x_{4}^{-1} x_{1}^{-1} x_{2} x_{4} x_{1} x_{5} x_{4}^{-1} x_{2}^{-1}\! x_{5}^{-1}\! x_{1}^{-1} x_{1} x_{3} x_{1} x_{5} x_{2} x_{4} x_{5}^{-1} x_{1}^{-1} x_{4}^{-1} x_{2}^{-1} x_{3}^{-1} x_{1}^{-1} x_{1} x_{4} x_{2} x_{3} x_{4}^{-1} x_{1}^{-1} x_{3}^{-1} x_{2}^{-1} x_{3} x_{6} x_{2} x_{3} x_{1} x_{4} x_{3}^{-1} x_{2}^{-1} x_{4}^{-1} x_{1}^{-1} x_{6}^{-1} x_{3}^{-1} x_{1} x_{6} x_{2} x_{5} x_{4} x_{6} x_{5}^{-1} x_{2}^{-1} x_{6}^{-1} x_{4}^{-1} x_{6}^{-1} x_{1}^{-1} x_{4} x_{6} x_{2} x_{5} x_{6}^{-1} x_{4}^{-1} x_{5}^{-1}x_{2}^{-1}x_{3} x_{5} x_{2} x_{6} x_{4} x_{5} x_{6}^{-1} x_{2}^{-1} x_{5}^{-1} x_{4}^{-1} x_{5}^{-1} x_{3}^{-1} x_{4} x_{5} x_{2} x_{6} x_{5}^{-1} x_{4}^{-1} x_{6}^{-1} x_{2}^{-1} x_{2} x_{5} x_{4} x_{6} x_{5}^{-1} x_{2}^{-1} x_{6}^{-1} x_{4}^{-1} x_{1} x_{6} x_{4} x_{6} x_{2} x_{5} x_{6}^{-1} x_{4}^{-1} x_{5}^{-1} x_{2}^{-1} x_{6}^{-1} x_{1}^{-1} x_{2} x_{6} x_{4} x_{5} x_{6}^{-1} x_{2}^{-1} x_{5}^{-1} x_{4}^{-1} x_{3} x_{5} x_{4} x_{5} x_{2} x_{6} x_{5}^{-1} x_{4}^{-1} x_{6}^{-1} x_{2}^{-1} x_{5}^{-1} x_{3}^{-1} x_{3} x_{6} x_{1} x_{4} x_{2} x_{3} x_{4}^{-1} x_{1}^{-1} x_{3}^{-1} x_{2}^{-1} x_{6}^{-1} x_{3}^{-1} x_{2} x_{3} x_{1} x_{4} x_{3}^{-1} x_{2}^{-1} x_{4}^{-1} x_{1}^{-1} x_{1} x_{3} x_{2} x_{4} x_{1} x_{5} x_{4}^{-1} x_{2}^{-1} x_{5}^{-1} x_{1}^{-1} x_{3}^{-1} x_{1}^{-1} x_{1} x_{5} x_{2} x_{4} x_{5}^{-1} x_{1}^{-1} x_{4}^{-1} x_{2}^{-1} x_{1} x_{4} x_{2} x_{3} x_{4}^{-1} x_{1}^{-1} x_{3}^{-1} x_{2}^{-1} x_{3} x_{6} x_{2} x_{3} x_{1} x_{4} x_{3}^{-1} x_{2}^{-1} x_{4}^{-1} x_{1}^{-1} x_{6}^{-1} x_{3}^{-1} x_{2} x_{4} x_{1} x_{5} x_{4}^{-1} x_{2}^{-1} x_{5}^{-1} x_{1}^{-1} x_{1} x_{3} x_{1} x_{5} x_{2} x_{4} x_{5}^{-1} x_{1}^{-1} x_{4}^{-1} x_{2}^{-1} x_{3}^{-1} x_{1}^{-1} x_{3} x_{5} x_{2} x_{6} x_{4} x_{5} x_{6}^{-1} x_{2}^{-1} x_{5}^{-1} x_{4}^{-1} x_{5}^{-1} x_{3}^{-1} x_{4} x_{5} x_{2} x_{6} x_{5}^{-1} x_{4}^{-1} x_{6}^{-1} x_{2}^{-1} x_{1} x_{6} x_{2} x_{5} x_{4} x_{6} x_{5}^{-1} x_{2}^{-1} x_{6}^{-1} x_{4}^{-1} x_{6}^{-1} x_{1}^{-1} x_{4} x_{6} x_{2} x_{5} x_{6}^{-1} x_{4}^{-1} x_{5}^{-1} x_{2}^{-1} x_{2} x_{6} x_{4} x_{5} x_{6}^{-1} x_{2}^{-1} x_{5}^{-1} x_{4}^{-1} x_{3} x_{5} x_{4} x_{5} x_{2} x_{6} x_{5}^{-1} x_{4}^{-1} x_{6}^{-1} x_{2}^{-1} x_{5}^{-1} x_{3}^{-1} x_{2} x_{5} x_{4} x_{6} x_{5}^{-1} x_{2}^{-1} x_{6}^{-1} x_{4}^{-1} x_{1} x_{6} x_{4} x_{6} x_{2} x_{5} x_{6}^{-1} x_{4}^{-1} x_{5}^{-1} x_{2}^{-1} x_{6}^{-1} x_{1}^{-1}\), where x 1 and x 2 are red, x 3 and x 4 are green, and x 5 and x 6 are blue.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Demaine, E.D., Demaine, M.L., Minsky, Y.N. et al. Picture-Hanging Puzzles. Theory Comput Syst 54, 531–550 (2014). https://doi.org/10.1007/s00224-013-9501-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-013-9501-0

Keywords

Search

Navigation