Matchstick Snakes
Ed Pegg Jr
involving matchstick snakes. The object is to find
the longest snake that fits inside a certain
area, without ever touching or crossing over itself.
Like all great problems, I initially dismissed it.
My first thought was that an infinite snake could be
made, but then I reread his careful rule specification
... the angles the snake could bend at were limited.
Recently, I started looking at the snakes bounded by
a 2x2 square, and where all angles were multiples of
30 degrees. A lot of people, including me, spent
some time studying these snakes, and many unexpected
solutions popped up. One person, Susan Hoover, trounced
all the rest of us with a delightful length 20
snake.
As a puzzle, in a 2x2 square, put 20 matchsticks end to
end so that all angles between two matchsticks are
multiples of 30 degrees, and so that each matchstick
only touches only those matches directly before or
after it in the snake.
I have the solution at my site. My own best solution was
a 15-length snake. Some of my better solvers sent 17-length
snakes, and then a few length 19 solutions trickled in.
I have already started looking at other degree multiples,
and other bounding areas. This looks like a rich problem.
I haven't the foggiest idea what size of 20-degree snake will
fit into a radius 2 circle, but I want to know.
--Ed Pegg Jr, www.mathpuzzle.com
Rainer Rosenthal
Ed Pegg Jr wrote
> A few weeks ago, Serhiy Grabarchuk sent me a problem
> involving matchstick snakes. The object is to find
> the longest snake that fits inside a certain
> area, without ever touching or crossing over itself.
>
> Like all great problems, I initially dismissed it.
> My first thought was that an infinite snake could be
> made, but then I reread his careful rule specification
> ... the angles the snake could bend at were limited.
>
Great!
Same category as "lost in a forest", provided by
Steven Finch on one of his moving home pages.
Please feel free to have heavy discussions here.
Lurking,
Rainer
-
Rainer Rosenthal
r.ros...@web.de
Doug Magnoli
segments of the snake. I presume they're 1 ?
-Doug Magnoli
[Remove the two and the three for email.]
Ed Pegg Jr
Dave Langers
> a 2x2 square, and where all angles were multiples of
> 30 degrees. A lot of people, including me, spent
> some time studying these snakes, and many unexpected
> solutions popped up. One person, Susan Hoover, trounced
> all the rest of us with a delightful length 20
> snake.
Using a brute-force approach, the best I could do was a 20-length snake
indeed. This should be the optimal solution for which not only the
angles between matchsticks are multiples of 30 degrees, but also the
angles between the matchsticks and the edges of the surrounding square.
It seems highly unlikely that there would be a solution for which the
matchstick snake starts under some other angle with respect to the
square, since even in Susan's solution 6 sticks lie on the edge of the
square.
The next question, regarding snakes in a circle, is somewhat more
difficult using my approach (any of you knows how to determine the
smallest circle that completely surrounds a given set of points?).
However, a triangle with sides 3 should be feasible. 2Bcontinued...
Bob Harris
> ... any of you knows how to determine the smallest circle that completely
> surrounds a given set of points? ...
Seems like an algorithm for this ought to be "well-known". But instead of
looking for one, I'll try to make one up.
Start by finding the two points A and B that are the farthest apart; call
this distance d. The circle we seek will have a diameter at least d.
Conceptually, all the points in the set must be within an (american)
football-shaped area that is the intersection of the circles of *radius* d
centered at A and B.
Take O as the midpoint of AB, and compute the distance of all points from O.
If none are farther than d/2, the circle at O through A and B is the
smallest. Otherwise, take the farthest point, C, and take the circle
through A, B, and C. Certainly no smaller circle will include A, B, and C.
But can any points be outside this circle (I don't know the answer)?
Bob H
Bob Harris
>> ... any of you knows how to determine the smallest circle that completely
>> surrounds a given set of points? ...
and I replied:
> Seems like an algorithm for this ought to be "well-known". But instead of
> looking for one, I'll try to make one up.
>
> Start by finding the two points A and B that are the farthest apart; call
> this distance d. The circle we seek will have a diameter at least d.
> Conceptually, all the points in the set must be within an (american)
> football-shaped area that is the intersection of the circles of *radius* d
> centered at A and B.
>
> Take O as the midpoint of AB, and compute the distance of all points from O.
> If none are farther than d/2, the circle at O through A and B is the smallest.
> Otherwise, take the farthest point, C, and take the circle through A, B, and
> C. Certainly no smaller circle will include A, B, and C. But can any points
> be outside this circle (I don't know the answer)?
The answer to the last question is "yes".
Bob H
Bob Harris
> ... any of you knows how to determine the smallest circle that completely
> surrounds a given set of points? ...
I tried a google search for
smallest circle containing set of points
and the first useful link that resulted was
http://www.delphiforfun.org/Programs/circle_covering_points.htm
Dave Langers
> indeed.
By the way, there is an alternate solution to this problem!
If I denote the subsequent directions of the matchsticks with
clock-directions (12 = up, 3 = right, 7 = 30 degrees left from down,
etc.), then Susan's snake at http://www.mathpuzzle.com/snake20.gif
follows the course:
6 8 3 12 12 9 9 6 1 6 3 10 3 10 3 6 8 10 5 2
and the alternate solution goes like:
12 5 12 9 6 6 3 3 12 12 8 6 11 6 11 6 3 1 6 9
Walter Baeck
That's a beautiful solution too.
As a fellow brute, I used a brute-force approach too,
but I ended up with the same solution as given by Ed.
I'm interested in your source code if you'd like to show it.
I would have posted mine, but it's 200 lines and I wouldn't
want to pull a Kabatoff on this newgroup.
Also, the algorithm for detecting intersection of two segments
has evolved into a major hassle, and it makes the whole program
look like an embarassment now.
It's on http://users.pandora.be/walter.baeck/Snake/index.html
if you care for it anyway.
What might be of interested is my solution (20 segments) for
the size-3 triangle challenge you hinted at in your previous post.
I also tried to get a result for Ed's extension to a radius-2
circle with 20-degree bends. But unlike the Square and Triangle
programs, Circle is still running after several days.
I think that the bounding area is oversized; the best result
obtained so far has 66 segments and it's not aesthetic at all.
--
____________
\ / Walter Baeck
\ ALCATEL/ Alcatel Telecom
\ BELL / Broadband Networks Division
\ / Microelectronics Design
\ / E-mail : walter...@alcatel.be
\/ Phone : +32 3 240 73 86
Dave Langers
> I would have posted mine, but it's 200 lines and I wouldn't
> want to pull a Kabatoff on this newgroup.
I'll send it to you by mail (it's BP7, quick-and-dirty and uncommented).
> What might be of interested is my solution (20 segments) for
> the size-3 triangle challenge you hinted at in your previous post.
I believe I have five different solutions with 21 segments. In
'clock-notation':
12 4 4 4 8 8 8 1 11 1 4 9 4 9 4 1 4 8 9 7 2
12 4 4 4 8 8 8 1 11 1 4 9 4 9 4 1 4 9 7 8 1
12 4 4 4 8 8 8 1 11 4 7 2 11 11 4 4 9 4 8 8 1
12 5 7 2 2 2 10 10 10 6 5 2 9 0 5 3 8 3 8 8 1
12 5 7 6 2 11 2 7 2 7 2 11 9 11 6 6 6 2 2 2 10
> I also tried to get a result for Ed's extension to a radius-2
> circle with 20-degree bends. But unlike the Square and Triangle
> programs, Circle is still running after several days.
> I think that the bounding area is oversized; the best result
> obtained so far has 66 segments and it's not aesthetic at all.
I agree; I've been running a 2x3-rectangle with 30-degree bends for a
day now: best so far is 34 segments.
How about a diameter-3 circle with 30-degree bends?
Dave Langers
> I agree; I've been running a 2x3-rectangle with 30-degree bends for a
> day now: best so far is 34 segments.
The optimum has 39 segments and has a beautiful (!) symmetry:
3 8 3 8 3 8 3 1 6 9 9 2 9 2 9 6 11 12 3 3 3 6 11 6 9 2 9 2 9 9 6 1 3 8 3
8 3 8 3
> How about a diameter-3 circle with 30-degree bends?
Maximum is 33 segments:
12 5 12 5 12 5 7 2 11 11 6 11 2 4 9 5 5 8 9 2 11 6 11 6 11 12 2 7 5 12 5
12 5 (R=1.498;Cx=0.746;Cy=0.892)