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