Chris Lusby Taylor

Hi Ed,

Neil Fitzgerald's approach works well, but his solution is far from

optimal for more than 3 pins.

By recursively adding just one nail at a time, he misses the possibility

of recursively splitting the nails into two smaller groups of

approximately equal size.

I propose to represent a solution for pins numbered a to c to be

s(a..c). Then,

Let s(n..n) = n

Let b = int((a+c)/2)

Then s(a..c) = s(a..b) s(b+1..c) !s(a..b) !s(b+1..c)

For instance, for 4 pins

s(1..4)=s(1..2) s(3..4) !s(1..2) !s(3..4)

= 1 2 !1 !2 3 4 !3 !4 2 1 !2 !1 4 3 !4 !3

s(1..5) = s(1..3) s(4..5) !s(1..3) !s(4..5)

= s(1..2) 3 !s(1..2) !3 4 5 !4 !5 3 s(1..2) !3 !s(1..2) 5 4 !5

!4

= 1 2 !1 !2 3 2 1 !2 !1 !3 4 5 !4 !5 3 1 2 !1 !2 !3 2 1 !2 !1 5

4 !5 !4

s(1..6) = s(1..3) s(4..6) !s(1..3) !s(4..6)

= 1 2 !1 !2 3 2 1 !2 !1 !3 4 5 !4 !5 6 5 4 !5 !4 !6

3 1 2 !1 !2 !3 2 1 !2 !1 6 4 5 !4 !5 !6 5 4 !5 !4

which is only 40 steps, against 64 in Neil's method.

I can see how to do it with n nails, never mind 5 or 6.

Basically, it's possible to reduce the problem to group theory (as is so

often the case...), where it becomes the following:

Given the free group with n generators...

(call it F[n], and denote the generators simply by "1, 2, ..., n",
let their

inverses be denoted by "!1, !2, ..., !n")

...try to find an element satisfying both of the following conditions:

(1) It cannot be formed without using all n generators (so that in

particular, it is not equal to the identity element, e).

(2) If any of the generators are 'quotiented out', the corresponding element

of the quotient group is the identity.

In less anally-retentive terms, what I mean is simply that if you write

down the expression, substituting e for any one of the generators, you get

an expression that can be simplifed to "e".

I'll demonstrate elements satisfying these conditions in a moment, but for

now I'll explain how to get from solutions of the group-theoretical problem

to solutions of the n-nail problem (well, more a description than an

explanation, in fact).

So, suppose we've found such an element, s(n) of F[n]. Here's how to solve

the n-nail problem:

(1) Write down s(n) in terms of the generators.

(2) Mark an arbitrary spot X on the wall - one that doesn't coincide with

any of the nails (which we'll refer to as N(1), ..., N(n)).

(3) Take a length of string and press one end (call this the L end, the

other being the R end) against the "X".

(4) Look at the first term in the expression of s(n), it will either of the

form r or !r, where r is in {1, ..., n}. If it is 'r', then, keeping the

end of the string against "X", wind the rest of it clockwise round
N(r) and

then return it to X. If it is '!r', go anti-clockwise.

(If (4) has just been carried out properly, The string should now have the

following form: The L end should be against X, then running R-wards along

it, it should loop around N(r) and then return to X, after which it goes to

some undefined location that we don't really care about)

(5) repeat (4) for the second term, third term etc. until you've got through

the entire expression, all the time keeping the L end against X.

(6) Assuming we haven't run out of string, we can now chop off the

remaining, unused section, and then tie the two ends (of the main section)

together. The string should now be a closed loop that cannot come free of

the nails, but if any nail is removed, it should be able to come free.

[ There may (quite literally) be a little bit of a snag here, because if the

loop becomes knotted, it will not necessarily come free - so you have to be

extra-careful when carrying out this procedure ]

Now for the solution to the group-theoretical problem:

Let s(1) = 1

Let s(n+1) = s(n) (n+1) !s(n) !(n+1)

I'll leave it as an exercise to the reader to prove that this solution

works, and that my procedure above does indeed convert valid solutions of

the group theoretical problem into valid solutions of the n-nail problem.

Just for the sake of completeness, I'll write down the solutions up to s(6):

s(1) = 1

s(2) = 1 2 !1 !2

s(3) = 1 2 !1 !2 3 2 1 !2 !1 !3

s(4) = 1 2 !1 !2 3 2 1 !2 !1 !3 4 3 1 2 !1 !2 !3 2 1 !2 !1 !4

s(5) = 1 2 !1 !2 3 2 1 !2 !1 !3 4 3 1 2 !1 !2 !3 2 1 !2 !1 !4 5 4 1 2 !1 !2

3 2 1 !2 !1 !3 !4 3 1 2 !1 !2 !3 2 1 !2 !1 !5

s(6) = 1 2 !1 !2 3 2 1 !2 !1 !3 4 3 1 2 !1 !2 !3 2 1 !2 !1 !4 5 4 1 2 !1 !2

3 2 1 !2 !1 !3 !4 3 1 2 !1 !2 !3 2 1 !2 !1 !5 6 5 1 2 !1 !2 3 2 1 !2 !1 !3 4

3 1 2 !1 !2 !3 2 1 !2 !1 !4 !5 4 1 2 !1 !2 3 2 1 !2 !1 !3 !4 3 1 2 !1 !2 !3

2 1 !2 !1 !6

(well that was fun. Notice that any diagram of a solution to the n-nail

problem would be virtually unintelligible for n >= 4)

Another exercise for the reader is to find a non-recursive way of specifying

the solution - this isn't very difficult (though it may a bit messy)...

Essentially, s(n) is just the initial segement of an infinite sequence which

is itself a minor variation on:

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 ... etc.

Yet another exercise is to prove that s(n) is an optimally short solution of

the group-theoretical problem.

(apologies for the rather arrogant tone - I'll soon "come down" from
the

post-solution high, something I'm sure you must be familiar with.)

The website is excellent, by the way, keep up the good work [:-)]

Neil Fitzgerald

--------------------------------------------------------------------------------------------

Hi Ed,

I found this two nails puzzle the first time in Quantum.

Brainteasers B 201: Strange painting, Quantum (May/June 1997) p13 (A. Spivak)

Strange painting. There is a painting on the wall of Dr. Smile's waiting

room. The unusual thing about this painting is the way it's hung. Dr. Smile

hammered two nails (instead of one) into the wall. He says that he wound

the picture wire around these nails in such a way that the painting would

fall if either the nail were pulled out. How did he do it?

See my page

http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/quantum/B201

If you replace the nails by rings, you get Borromean rings.

Brunn has generalzed this to n interlocking rings. See

- H. Brunn;

\"Uber Verkettungen,

Sitzungsbericht der Bayerischen Akademie der Wissenschaft Mathematisch

Naturwissenschaftliche Abteilung 22 (1892) 77

(Borromean rings and their generalizations)

- Walter Lietzmann;

Anschauliche Topologie,

R. Oldenbourg Verlag, M\"unchen, 1955

- I.VI.12 Verkettungen (p80-83)

(Borromean rings and their generalizations)

I have not seen [Brunn]. [Lietzmann] shows the configuration in

such a way, that you can it apply it diretly to the n nails problem.

Yours Torsten Sillke