How to generalise hang picture puzzle?

Question

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?

Answer 1

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}

Answer 2

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