Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

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?

share|improve this question
    
I believe it should be possible, but it gets exponentially harder as $M$ increases. –  Joe Z. Jun 12 at 13:20

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Thank you, that is interesting. If you don't mind, please check my solution, does it looks correct for you? –  klm123 Jun 12 at 15:51
1  
Actually, now you was half an hour faster:) –  klm123 Jun 12 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).
share|improve this answer
    
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 at 16:59
    
@Bobson, this works by definition of F(1,...,K). Thank you for checking. –  klm123 Jun 12 at 17:18

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.