Snakes... on a Plane!
Christopher Night
are at least one. You may think of a snake as a curve with one end called
the snout, one end called the tail, and the rest called the middle. Snakes
can't overlap or cross each other, because, you know, they're on a plane.
Every snake is touching exactly three other snakes - one with its snout,
one with its middle, and one with its tail - and every snake is touched by
one snake snout, one snake middle, and one snake tail. No two snakes touch
each other in more than one place, and no snake touches itself. Also, no
two snakes touch snout to snout, middle to middle, or tail to tail.
What's the minimum number of snakes on the plane satisfying these
conditions?
-Christopher
PS: There's a subtle movie reference hidden somewhere in the title of this
puzzle. Bonus points if you find it!
William Elliot
> A 2-dimensional plane contains every snake in this puzzle, of which there
> are at least one. You may think of a snake as a curve with one end called
> the snout, one end called the tail, and the rest called the middle. Snakes
> can't overlap or cross each other, because, you know, they're on a plane.
>
> Every snake is touching exactly three other snakes - one with its snout,
> one with its middle, and one with its tail - and every snake is touched by
> one snake snout, one snake middle, and one snake tail. No two snakes touch
> each other in more than one place, and no snake touches itself. Also, no
> two snakes touch snout to snout, middle to middle, or tail to tail.
>
> What's the minimum number of snakes on the plane satisfying these
> conditions?
>
Three
> PS: There's a subtle movie reference hidden somewhere in the title of this
> puzzle. Bonus points if you find it!
>
Bonus points bah. Bonus points for using credit card, bonus points for
this and that. Bonus points tossed like a bone to a dog for doing a
trick. Bah, eat three humbugs and get a good night's sleep.
Richard Sabey
> Every snake is touching exactly three other snakes - one with its snout,
> one with its middle, and one with its tail - and every snake is touched by
> one snake snout, one snake middle, and one snake tail.
>Also, no
> two snakes touch snout to snout, middle to middle, or tail to tail.
For any snake X, either
1) X's snout touches a middle, X's middle a tail and X's tail a snout,
or
2) X's snout touches a tail, X's tail a middle and X's middle a snout.
Make a graph with a node for each snake, and with an arc XY wherever
snakes X and Y touch. Then the graph is cubic (i.e. each node is
adjacent to 3 others), which means that, for some integer k, there are
3k arcs, 2k nodes and 2k (an even number of) snakes.
Any two snakes that touch are of different types, so the graph is
bipartite, so all its cycles are of even length.
>No two snakes touch
> each other in more than one place, and no snake touches itself.
So none of these cycles is a 2-cycle; each is a 4-cycle at least.
If there are 6 snakes, there are 3 of each type, and each snake touches
each snake of the opposite type. Thus the graph is K3,3 which is not
planar. However,
> A 2-dimensional plane contains every snake in this puzzle, of which there
> are at least one.
Thus there are at least 8 snakes. One (the only?) planar cubic
bipartite 8-node graph with no 2-cycles is that corresponding to a
cube, the graph's nodes being the cube's vertices and the graph's arcs
being the cube's edges. Alternatively, the graph corresponds to a
regular octahedron, the graph's nodes and the snakes being the
octahedron's faces, and the graph's arcs being the octahedron's edges.
Colour the faces of the octahedron alternatively black and white, and
put on every black face a snake coiling clockwise, and on every white
face a snake coiling anticlockwise:
m t
+--------+--------+
| t /|\ m |
| / | \ |
| / | \ |
s|m s/ | \t s|m
| /t m|t s\ |
| / | \ |
| / | \ |
|/ s | m \|
+--------+--------+
|\ m | s /|
| \ | / |
| \ | / |
| \s t|m t/ |
m|s t\ | /s m|s
| \ | / |
| \ | / |
| m \|/ t |
+--------+--------+
t m
Simon Tatham
> Alternatively, the graph corresponds to a regular octahedron, the
> graph's nodes and the snakes being the octahedron's faces, and the
> graph's arcs being the octahedron's edges. Colour the faces of the
> octahedron alternatively black and white, and put on every black
> face a snake coiling clockwise, and on every white face a snake
> coiling anticlockwise:
Nice solution. Reducing it to a simple planar diagram containing
nothing but snakes, we get the following pleasantly near-symmetric
arrangement:
AaaaaaaaaBbbb
c a b
c a b
ceeeeeEff b
c H f b
c h F b
c hhGgggggb
c d b
c d b
cccCddddddddD
where each letter, of course, represents part of a different snake,
and a capital represents the snout.
--
Simon Tatham "A defensive weapon is one with my finger on the
<ana...@pobox.com> trigger. An offensive weapon is one with yours."
Patrick Hamlyn
>On Thu, 17 Aug 2006, Christopher Night wrote:
>
>> A 2-dimensional plane contains every snake in this puzzle, of which there
>> are at least one. You may think of a snake as a curve with one end called
>> the snout, one end called the tail, and the rest called the middle. Snakes
>> can't overlap or cross each other, because, you know, they're on a plane.
>>
>> Every snake is touching exactly three other snakes - one with its snout,
>> one with its middle, and one with its tail - and every snake is touched by
>> one snake snout, one snake middle, and one snake tail. No two snakes touch
>> each other in more than one place, and no snake touches itself. Also, no
>> two snakes touch snout to snout, middle to middle, or tail to tail.
>>
>> What's the minimum number of snakes on the plane satisfying these
>> conditions?
>>
>Three
Eh?? No bonus for you. Snake A has to touch *three other snakes*. That's a
minimum of four snakes right there. Go to bed without a humbug.
Christopher Night
[reasoning snipped]
> Thus there are at least 8 snakes. One (the only?) planar cubic
> bipartite 8-node graph with no 2-cycles is that corresponding to a
> cube, the graph's nodes being the cube's vertices and the graph's arcs
> being the cube's edges. Alternatively, the graph corresponds to a
> regular octahedron, the graph's nodes and the snakes being the
> octahedron's faces, and the graph's arcs being the octahedron's edges.
> Colour the faces of the octahedron alternatively black and white, and
> put on every black face a snake coiling clockwise, and on every white
> face a snake coiling anticlockwise:
[diagram snipped]
Excellent solution! I was able to reason that there were at least 8
snakes, but not construct a solution as you did above. Instead I just
played around and found one (which is apparently equivalent to yours):
http://tinyurl.com/5181s/snakes-on-a-plane.jpg
Thanks for responding. That was my first real puzzle. I hope you enjoyed
it!
-Christopher
nobody
Four snakes is the minimum, as shown below. The four snakes
are represented by the letters a,b,c and d, where a capital
letter is the snout.
dddddddddddd
d C d
d c D
d c aaaaaaa
d c a
d c a
AbbbbbbbbB a
a a
a a
aaaaaaaaaaaaaaaaaa
Arthur J. O'Dwyer
>> one with its middle, and one with its tail - and every snake is touched by
>> one snake snout, one snake middle, and one snake tail. No two snakes touch
>> each other in more than one place, and no snake touches itself. Also, no
>> two snakes touch snout to snout, middle to middle, or tail to tail.
> Four snakes is the minimum, as shown below. The four snakes
> are represented by the letters a,b,c and d, where a capital
> letter is the snout.
>
> dddddddddddd
> d C d
> d c D
> d c aaaaaaa
> d c a
> d c a
> AbbbbbbbbB a
> a a
> a a
> aaaaaaaaaaaaaaaaaa
Snake "D" is touched by two snake middles.
-Arthur
drrd...@earthlink.net
Everywhere I turn, it's more snakes in planes:
http://www.maa.org/editorial/mathgames/mathgames_08_17_06.html
Aieeeeeee! :-)
Doug Chatham
d dot chatham at moreheadstate dot edu
Rainer Rosenthal
> Everywhere I turn, it's more snakes in planes:
> http://www.maa.org/editorial/mathgames/mathgames_08_17_06.html
>
> Aieeeeeee! :-)
And they are dangerous and will attack on Monday, as can be
seen in the middle of the link above:
http://recmath.org/contest/index.php
Keep cool: you may kill them until Tuesday 11/21/2006 11:00:00 GMT.
Best regards,
Rainer Rosenthal
r.ros...@web.de
Keith A. Lewis
That's allowed. However, it is *not* touched by any tail, which makes this
a non-solution.
--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
Ed Murphy
"A snake cannot be touched by the same part more than once" can be
derived from the given rules, using the pigeonhole principle.
Arthur J. O'Dwyer
On Wed, 23 Aug 2006, Ed Murphy wrote:
>
> On Tue, 22 Aug 2006 16:51:02 +0000 (UTC), kle...@LUMINA.MITRE.ORG
> (Keith A. Lewis) wrote:
>> "Arthur J. O'Dwyer" <ajon...@andrew.cmu.edu> writes in article <Pine.LNX.4.60-041....@unix43.andrew.cmu.edu> dated Thu, 17 Aug 2006 22:03:13 -0400 (EDT):
>>> On Fri, 18 Aug 2006, nobody wrote:
>>>> Christopher Night <ni...@fas.harvard.edu> wrote in news:
>>>>>
>>>>> one snake snout, one snake middle, and one snake tail.
>>> Snake "D" is touched by two snake middles.
>>
>> That's allowed. However, it is *not* touched by any tail, which makes this
>> a non-solution.
>
> "A snake cannot be touched by the same part more than once" can be
> derived from the given rules, using the pigeonhole principle.
True, but I was actually using the rule left quoted above: "Every
snake is touched by ... one snake middle." (It's a well-known problem
in mathematics that whenever you say "N" without a qualifier, one person
will interpret it as meaning "exactly N", and one person will interpret
it as meaning "at least N." I chose the former; Keith chose the latter.
Ed points out that my interpretation was the more correct in this case.)
-Arthur,
corollary: Any paper using "N" without a qualifier is read by at most
two people.
Christopher Night
> On Wed, 23 Aug 2006, Ed Murphy wrote:
> > (Keith A. Lewis) wrote:
> >> "Arthur J. O'Dwyer" <ajon...@andrew.cmu.edu> writes
> >>>> Christopher Night <ni...@fas.harvard.edu> wrote in news:
> >>>>>
> >>>>> every snake is touched by
> >>>>> one snake snout, one snake middle, and one snake tail.
> [...]
> >>> Snake "D" is touched by two snake middles.
> >>
> >> That's allowed. However, it is *not* touched by any tail, which makes this
> >> a non-solution.
> >
> > "A snake cannot be touched by the same part more than once" can be
> > derived from the given rules, using the pigeonhole principle.
>
> True, but I was actually using the rule left quoted above: "Every
> snake is touched by ... one snake middle." (It's a well-known problem in
> mathematics that whenever you say "N" without a qualifier, one person
> will interpret it as meaning "exactly N", and one person will interpret
> it as meaning "at least N." I chose the former; Keith chose the latter.
> Ed points out that my interpretation was the more correct in this case.)
>
> -Arthur,
> corollary: Any paper using "N" without a qualifier is read by at most
> two people.
Hey, give me a little credit! I would have qualified it if it was
ambiguous. As Ed points out, taking the other rules into consideration,
it's impossible for a solution to be valid under one interpretation but
not the other. I think that neither your interpretation nor Keith's is
more correct; rather, it doesn't matter.
As it is, I took great care in omitting needless words from the problem
statement; I know you people are too busy to waste your time reading three
redundant "exactly"s. ;-)
-Christopher