Nails and strings and paintings

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.

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...

Solution 1:

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 $\{\}$.

Solution 2:

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.