Saturday, April 26, 2008

Solution to many-pinned paintings

See the original puzzle

I've prepared my own picture of the double-pinned solution: see it here

Have I ever mentioned that I hand out free Technorati authority to solvers?

Susan of Intrinsically Knotted solved this puzzle by considering the Borromean rings. The Borromean rings are a set of three rings that are linked together in such a way that breaking any single ring will unlink the other two. All you need to do is transform two of the rings into pins, and you've got a solution. See her visual presentation here.

Warning: Advanced puzzle-solving to follow!

In the general case, we have the painting hung on N pins. Removing any M pins will cause the painting to fall, but removing any M-1 pins will leave it hanging.

You'll find that drawing any solution with more than two pins quickly becomes impossible. Therefore, it is essential that we have a compact naming system to describe any solution. In the solution, we will have N pins side by side. Each one will be associated with a letter. The leftmost pin is A, the next is B, and so on. We must wind the string of the painting above and below these pins. I will use a capital letter to signify going above the corresponding pin, and a small letter to signify going below the corresponding pin.

For example, the solution to the double pinned painting can be described by the following sequence: AbBAaB

I find this naming system convenient, because you can always tell when the painting will fall. For example, if you remove pin B from the above solution, we're left with "AAa" The two capital 'A's will cancel, for obvious reasons, and we'll be left with a. In other words, the entire string is below the pin, and will therefore fall down.

I will create a recursive algorithm that generates a general solution. The solution produced by this algorithm for values of N and M will be called S(N,M). The reverse of this solution will be called R(N,M). For example, S(2,1) = AbBAaB, and R(2,1) = BaABbA.

There are two trivial cases for which the solution is obvious:

S(N,0) = abcd...
S(N,N) = ABCD...

For nontrivial cases, the solution can always be given by the following (where the letter associated with the rightmost pin is X):

S(N,M) = S(N-1,M) xX R(N-1,M) S(N-1,M-1) X

We know this solution works because: (1) if we remove pin X, we're left with S(N-1,M-1), and(2) if we leave pin X, we must remove M pins, leaving us with sequence "xXX", which falls.

Here are a few instances of S(N,M):

S(3,1) = AbBAaBcCBaABbAabC [This is fun, isn't it?]
S(3,2) = ABcCBbBAaBC [I'm doing these by hand!]
S(4,2) = ABcCBbBAaBCdDCBaABbBCcBbBAaBcCBaABbAabCD [Maybe synesthesia would help?]
S(5,4) = ABCDeEDdDCcCBbBAaBCDE [Don't stop me now!]
S(6,3) = ABCdDCcCBbBAaBCDeE... [ok, maybe I should stop]