Task A

Task B

How I found the solution

The story began when I attended the Sonya Kovalevsky math days at KTH 2001 and we were given this problem. Task A me and my partner solved by hand but we never figured out the solution to task B. It was just too hard. I thought about it on and off for seven years and finally solved it.

I solved it by writing an exhaustive search algorithm. The shortest solution turned out to be 10 steps long. At each step the algorithm has five options (clockwise or counter-clockwise around nail 1, 2 or 3 minus the option to go back where it came from). The search tree therefore contains ~10 million nodes. You could probably prune the search tree further by taking symmetry into account. The algorithm is not flawless as it ignores the fact that the thread can pass itself by either going above or below. This however did not turn out to be an issue for the 3 nail problem. (Could it ever be an issue??)

The obvious task C is to do it for 4 nails. I'm currently letting my algorithm search for such a solution but I have little hope that it will find anything in feasible time. With my current optimizations it would take at least 2 months to search to a depth of 15 steps. And even that is a bit optimistic since the complexity rose from 4 steps to 10 going from 2 nails to 3.

Please send your comments to andreas dot lundblad at gmail dot com.