Yes. You can.
First, let's reformulate the puzzle to mathematical language.
- We place all nails on one straight line L and take some point P, far away from line L and all nails on it.
- We number all nails from 1 to N.
- 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
- Let's note several operations, which are done one after another (with nails A, B, ..., Z) as
S = O(A)O(B)..O(Z), let's denote
S* = O*(Z)..O*(B)O*(A).
- Let's note operator, which does nothing as
- 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.
Second, let's investigate properties of the operator
O(...) and it's combinations
E = E*.
O**(X) = O(X).
- 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.
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.
UU* = E.
Then, let's solve the puzzle for M = 1.
- Let's note the sequence of operations, that solves the task for N nails 1,2,..,N as
- If N = 1. Trivial solution is
F(1) = O(1).
- 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.
- 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).
Now, M > 1.
- Let's note the sequence of operations, that solves the task with N and M as
- 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.
- 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
R = N choose M. For each combination we can consider operator G:
- 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.
- 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
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
S(K,M) will become E and the picture will fall.
- 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).