How to generalise hang picture puzzle?

There is well known problem:

The picture is attached to a string and you want to hang it on N nails so that if one takes out any of the nails, the picture falls. How do you do it?

For those who have not heard this puzzle:
No brainteaser tricks are here, this is basically topology problem: "How to put N points and a closed curve on a plane in a way that curve can't be moved to infinity without crossing any point, but if one arbitrary point is removed - it can?"

Is it possible to generalise in the following way?:

The picture is attached to a string and you want to hang it on N nails so that if one takes out any M of the N nails, the picture falls, but if one takes out any M-1 nails the picture will not be freed. How do you do it?

Does this problem have a solution? Can it be shown that this is impossible to do if M > 1?

-
I believe it should be possible, but it gets exponentially harder as $M$ increases. –  Joe Z. Jun 12 '14 at 13:20

There's a paper available on the arXiv* which investigates both the "remove one nail" variant (which they call "1-of-\$n\$") and a more generalized "\$k\$-of-\$n\$" version (remove \$k\$ out of \$n\$ nails to make the picture fall).

Theorem 1, on page 18 addresses the \$1\$-of-\$n\$ version:

Theorem 1 For any \$n \geq 1\$, there is a picture hanging on \$n\$ nails of length at most \$2n^2\$ that falls upon the removal of any one nail. For each \$i = 1, 2, ..., n\$, symbols \$x_i\$ and \$x_i^{-1}\$ appear at most \$2n\$ times.

I'm not going to reproduce the whole proof here, because it involves more LaTeX than I want to try and transcribe, but the gist of it (if I'm understanding it correctly) is:

1. We have \$n = 1\$ and \$n = 2\$ solutions.
2. We can show that any problem's solution is equivalent to splitting the problem in half and solving each half, then looping them together.
3. All problems can be recursively reduced to a series of \$n =1\$ or \$n = 2\$ problems.

* Paper source: arXiv:1203.3602v2 [cs.DS] 26 Apr 2014

-
Thank you, that is interesting. If you don't mind, please check my solution, does it looks correct for you? –  klm123 Jun 12 '14 at 15:51
Actually, now you was half an hour faster:) –  klm123 Jun 12 '14 at 17:43

Yes. You can.

1. First, let's reformulate the puzzle to mathematical language.

1. We place all nails on one straight line L and take some point P, far away from line L and all nails on it.
2. We number all nails from 1 to N.
3. We take the string; place one end at P; move the other end around some nail number X clockwise; move the end back to point P. Let's note all this operations as O(X). Let's note the same operation, but done anticlockwise as O*(X).
4. Let's note several operations, which are done one after another (with nails A, B, ..., Z) as O(A)O(B)..O(Z).
5. If S = O(A)O(B)..O(Z), let's denote S* = O*(Z)..O*(B)O*(A).
6. Let's note operator, which does nothing as E.
7. Now our task is reformulated like this: find sequence of operators, which is not E when you remove any M-1 nails, and is E when you remove M nails.
2. Second, let's investigate properties of the operator O(...) and it's combinations U.

1. E = E*.
2. O**(X) = O(X).
3. If we take some nail X out then O(X) will become E. In sequence of operations we should remove all O(X) and O*(X). Since topologically these operations will do nothing.
4. O(X)O*(X) = E. If in sequence of operations we have O(X)O*(X) we can remove it. Since topologically these operations will do nothing.
5. UU* = E.
3. Then, let's solve the puzzle for M = 1.

1. Let's note the sequence of operations, that solves the task for N nails 1,2,..,N as F(1,2,..,N).
2. If N = 1. Trivial solution is F(1) = O(1).
3. If N = K+1. Suppose that we solved N = K already (we can do it similarly to mathematical induction method). Solution is defined recursively from solution for K nails: F(1,..,K,K+1) = F(1,...,K)O(K+1)F*(1,...,K)O*(K+1). This works because if you take one nail X <= K out F(1,...,K) will become E and F(1,..,K,K+1) will became O(K+1)O*(K+1) = E, if you take nail K+1 out O(K+1) will become E and F(1,..,K,K+1) will became F(1,..,K)F*(1,..,K) = E.
4. For example, solution for 3 nails is: F(1,2,3) = O(1)O(2)O*(1)O*(2)O(3)O(2)O(1)O*(2)O*(1)O*(3).
4. Now, M > 1.

1. Let's note the sequence of operations, that solves the task with N and M as S(N,M).
2. Let's invent sequence G(X1,X2,..,XM), which is not E until you remove all nails among X1,X2,..,XM. It is quite trivial: G(X1,X2,..,XM) = O(X1)O(X2)..O(XM) - we just must hang the picture on all nails as one.
3. Let's consider all possible combinations of M nails out of N: 1,2,..,M-1,M; 1,2,..,M-1,M+1; ... N-M+1,N-M+2,..,N-1,N; Let's number them and call them C1,C2,..,CR, where R = N choose M. For each combination we can consider operator G: G(Ck).
4. Now we need to do the same procedure as we did with M=1, but instead of nails use combinations of nails. The solution is given recursively, in R steps: S'(1,M) = G(C1); S'(k+1,M)=S'(k,M)G(Ck)S'*(k,M)G*(Ck), here k is number of k-th combination, S'(k,M) the sequience, which solves the task for first k combinations. Therefore S'(k,M) will work when you remove groups of nails, which belong to any combinations from 1 to k.
5. The required solution is S(K,M) = S'(N choose M,M). Indeed, if we remove one nail, neither combination from Ck will not become E, therefore S(K,M) will not become E and the picture will not be freed. If we remove any M nail, the removed nails are compose one combination from Ck, then S(K,M) will become E and the picture will fall.
6. For example, solution for N=3, M=2 is: S(3,2) = G(C1)G(C2)G*(C1)G*(C2)G(C3)G(C2)G(C1)G*(C2)G*(C1)G*(C3) = O(2)O(3)O(3)O(1)O*(3)O*(2)O*(1)O*(3)O(1)O(2)O(3)O(1)O(2)O(3)O*(3)O*(1)O*(3)O*(2)O*(2)O*(1).
-
This works because if you take one nail X <= K out F(1,...,K) will become E -> Why is this true? I would only expect O(X) to become E. Please elaborate. Other than that, it does seem to match the algorithm and results in the paper I linked. Good writeup. –  Bobson Jun 12 '14 at 16:59
@Bobson, this works by definition of F(1,...,K). Thank you for checking. –  klm123 Jun 12 '14 at 17:18