Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is based on the "Picture proof" challenges from Rankk.org...

IDEA: You want to hold up a painting using nails on a wall and string. The string is attached to the left and right sides of the painting and the nails are in between (let's say in a horizontal straight line for simplicity).

QUESTION: The object is to find ways of doing this to satisfy various requirements. For example, so that if any one nail is taken out, it will fall. Or so that if any two nails (but not one) are taken out it will fall. In particular, I want to find short solutions or even a method to construct all possible solutions. Basically, what exactly is the mathematical structure and what are the main results or whatever.

VISUALS: Here I use capitals for the inverses.

Incredible drawings

THEORY: First nomenclature. Let's say we have three nails: $a$, $b$ and $c$. If we pass over the first nail rightwards, we call that $a$, but if we go over it leftwards, we call that $a^{-1}$. Then if we conatenate or multiply them, it means we do one after another. So for example, $abc$ corresponds to the string going across over the top of all the three nails from left to right. In that case, all three nails would need to be removed before the painting fell. Something like $aba^{-1}$ means it's looped around $b$ but sort of hanging on $a$ as well. Only $b$ needs to be removed for it to fall.

Obviously $aa^{-1}$ cancels out. And $a^5$ means a bunch of loops. Removing a nail simply means removing all of its appearances in the formula. The painting will fall if the whole thing reduces to the identity. Eg) $bca^{-1}cac$ becomes $bc^3$ if the $a$ nail is taken out. Perhaps the most powerful tool I've found is that you can use a kind of conjugation as an "or" operator. It entangles the two parts. For example, $aba^{-1}b^{-1}$ will fall if either $a$ or $b$ are removed. The complement "and" operator is just multiplication. So $abcb^{-1}a^{-1}c^{-1}$ is $ab$ conjugated with $c$ and will fall if $c$ is removed or both $a$ and $b$.

As a starting point, who can find a short string for four nails that falls if any two are taken out?

PS. I can give more examples...

share|improve this question
    
Interestingly, your OR operator applied to $a$ and $a$ gives the identity... –  Rahul Jan 5 '12 at 5:22
    
@RahulNarain Yeah, it's a special case which has equivalents in many areas of maths. Another "problem" is $a$ "and" $a^{-1}$. Both of them hold up a painting, but together, they collapse. –  user826788 Jan 5 '12 at 5:55
    
It might just be me, but I'm having a hard time visualizing what you are talking about. A picture with actual nails and string would be helpful. –  Austin Mohr Jan 5 '12 at 6:12
    
@AustinMohr Fixed, I'm sure you're not the only one! abcABC is interesting because it needs exactly two nails taken out... –  user826788 Jan 5 '12 at 6:45
    
@user826788: That's interesting; can you name some of those equivalents? –  Rahul Jan 5 '12 at 7:26

2 Answers 2

A possible solution (in the first situation, that is we require exactly one nail to be pulled out in order for the picture to fall down) for nails $\alpha_1, \dots, \alpha_n$ would be the iterated commutator: $\gamma = [\alpha_1,\dots, \alpha_n]$, where $[a_1,a_2] = a_1a_2a_1^{-1}a_2^{-1}$ and $[a_1, \dots, a_n,a_{n+1}] = [[a_1,\dots, a_n],a_{n+1}]$.

The problem is completely described in the following way: Find an element $\gamma$ of the free group $F$ on generators $\alpha_1, \dots, \alpha_n$, such that $\gamma$ is not trivial and lies in the kernel of all the projection maps $F \to F/\langle \alpha_k \rangle$.

Now for the challenge at the end of your post: Let $\{a_1,a_2,a_3\} := a_1a_2a_3a_1^{-1}a_2^{-1}a_3^{-1}$. An element $\gamma$ of the free group $F$ generated by $\alpha_1,\alpha_2,\alpha_3,\alpha_4$, which is not trivial, whose projections $F \to F/\langle \alpha_k\rangle$ are not trivial but which lies in the kernel of the projections $F \to F/\langle \alpha_k, \alpha_j \rangle$ whenever $k \neq j$ is given by $\gamma = [\{\alpha_1,\alpha_2,\alpha_3\},\{\alpha_1,\alpha_2,\alpha_4\},\{\alpha_1,\alpha_3,\alpha_4\},\{\alpha_2,\alpha_3,\alpha_4\}]$. It should now be pretty easy to see how to generalize these results (using more nails, or requiring more nails to be pulled out) using only $[]$ and $\{\}$.

share|improve this answer
    
Thanks for the contribution! I actually already have that solution for the 1 nail case and it can sort of be improved on. For three nails it's fine: [[a,b],c] is equal best. For four nails it's better to use [[a,b],[c,d]] than [[[a,b],c],d]. Pretty interesting, huh? I don't think your answer for the two nail challenge is optimal. Like, what's the actual string in $a, b, c, d$? Also, I think this approach is perfectly "correct" but too abstract and weak. Finding optimal strings and classifying every possibility requires something richer and more sophisticated than free groups... –  user826788 Jan 5 '12 at 6:59
    
Sorry, just adding: [a,b,c] = abABcbaBAC (10). In general, the iterated commutator will give $3\times2^{n-1}-2$. But [[a,b],[c,d]] has length 16 compared to [a,b,c,d] which is 22. Other questions that arise are how many strings of length 16 are there? Or 18 or 20 or 22? How many different "types" are there? –  user826788 Jan 5 '12 at 7:08
    
Well what you really want is a set of free generators for $\bigcap_{k=1}^n \text{ker}(F \to F/ \langle \alpha_k \rangle)$ (in the case of the one nail problem). Such a set exists by the Nielsen-Schreier theorem but can well be infinite (and probably is in your case). As for optimal solutions it should be possible to show, that nested commutators (in a way representing a binary tree with minimal height for given number of leaves) is optimal. The two nail case should be much trickier. –  Alexander Thumm Jan 5 '12 at 9:47

Relevant: Picture-Hanging Puzzles by Demaine et al:

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.

"All monotone Boolean functions" means the following: Suppose you have a set $S$ of nails, and you select a family $\mathcal F$ of subsets of $S$. You remove some subset $S'$ of nails from the wall, and you want the picture to fall if and only if $S'\in\mathcal F$.

It is possible to hang the picture so that it falls only if a set of nails $S'$ is removed that is in $\mathcal F$ if and only if $\mathcal F$ has the following properties:

  • If $S'$ is an element of $\mathcal F$, so is any superset of $S'$.

  • If $S'$ is not an element of $\mathcal F$, the neither is any subset of $S'$.

So for example, if you want the picture to fall if nails $A$ and $B$ are removed, you have to agree that it will also fall if $A$, $B$, and some other nails are removed, and if you want the picture to stay up if only $A$ and $B$ are removed, you have to agree that it will also stay up if only $A$ or only $B$ is removed.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.