Hanging Picture Puzzle

Source: Mailed to me by Sudeep Kamath (PhD Candidate UC Berkeley, EE IITB 2008 Alumnus)

Problem:

Suppose we have a portrait hung on a wall using one nail. Now, suppose we hammer another nail next to the existing one and try to use both nails to hang the portrait. If any nail breaks, the portrait continues to hang safely. Can we hang the portrait in such a way that if any one nail breaks the portrait must fall down?

Generalize to k nails: Hang a portrait on k nails such that if any one nail breaks, the portrait must fall down.




Solution:

Highlight the part between the * symbols for the answer.
* Yes, for every k. Think of the string as a word in the nails: passing clockwise around nail i writes the letter i, counter-clockwise writes i^-1. The picture hangs iff the word is non-trivial (cannot be cancelled away), and it falls when, after deleting every occurrence of the broken nail's letter, the remaining word cancels to nothing.

Two nails: loop the string around nail 1 clockwise, then nail 2 clockwise, then nail 1 counter-clockwise, then nail 2 counter-clockwise: the commutator word 1.2.1^-1.2^-1. It is non-trivial, so the picture hangs. Break nail 1: deleting the 1's leaves 2.2^-1, which cancels - the string slides off and the picture falls. Same for nail 2.

k nails (induction): suppose W is a word in nails 1..k-1 that hangs the picture but falls as soon as any one of them breaks. Then the word W.k.W^-1.k^-1 works for nails 1..k. It is non-trivial (in the free group no cancellation occurs across the fresh letter k, so the word does not cancel away), hence the picture hangs. If nail k breaks, the word becomes W.W^-1, which cancels. If nail i < k breaks, W cancels by induction and the word collapses to k.k^-1, which cancels. Starting from W = 1.2.1^-1.2^-1 this builds a hanging for any k nails; the word length grows as L(k) = 2.L(k-1) + 2, i.e. L(k) = 3.2^(k-1) - 2 letters.

This is exactly the Brunnian phenomenon from topology (the same idea as Brunnian links and the picture-hanging puzzles of Demaine et al.): the whole hangs together, but cutting any one strand makes everything fall.

(solution posted by AI) *

Comments

  1. JDGM7:47 PM, December 05, 2012

    Cheeky little back-of-the-envelope sketch.

    ReplyDelete
  2. Anonymous2:45 AM, December 13, 2012

    What if all the nails are vertically aligned and you hang the picture on the lowest nail.

    ReplyDelete
    Replies
    1. INNER VOICE11:16 PM, December 19, 2012

      It says if any nail breaks, the portrait should fall down which doesn't happen in your case right.

      Delete
  3. Pratik Poddar12:24 AM, December 26, 2012

    @Jim,

    You assume that the picture is actually just literally hanging on a string. I believe the standard hanging picture puzzle assumes that the picture has two points where strings are fixed, much like tied on nails on the picture. With that assumption, your solution will not work.

    But given your assumption, I think your solution is great and amazing.

    Thanks a ton.

    ReplyDelete
  4. JDGM11:35 AM, December 31, 2012

    Fair enough, Pratik. Easily remedied :)

    ReplyDelete
  5. Vivek 7:42 PM, April 19, 2013

    This comment has been removed by the author.

    ReplyDelete
  6. Vivek 4:57 AM, April 20, 2013

    This comment has been removed by the author.

    ReplyDelete

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more