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?
-Christopher
PS: There's a subtle movie reference hidden somewhere in the title of this puzzle. Bonus points if you find it!
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
> 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.
Christopher Night wrote: > 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
Richard Sabey <richardsa...@hotmail.co.uk> wrote: > 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."
William Elliot <ma...@hevanet.remove.com> wrote: >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.
>> 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.
> 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):
> 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?
> -Christopher
> PS: There's a subtle movie reference hidden somewhere in the title of this > puzzle. Bonus points if you find it!
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
On Fri, 18 Aug 2006, nobody wrote: > Christopher Night <ni...@fas.harvard.edu> wrote in news:
>> 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. > 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
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?
> -Christopher
> PS: There's a subtle movie reference hidden somewhere in the title of this > puzzle. Bonus points if you find it!
>On Fri, 18 Aug 2006, nobody wrote: >> Christopher Night <ni...@fas.harvard.edu> wrote in news:
>>> 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.
>> 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.
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.
(Keith A. Lewis) wrote: >"Arthur J. O'Dwyer" <ajonos...@andrew.cmu.edu> writes in article <Pine.LNX.4.60-041.0608172202200.11...@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:
>>>> 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.
>>> 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.
>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.
> On Tue, 22 Aug 2006 16:51:02 +0000 (UTC), kle...@LUMINA.MITRE.ORG > (Keith A. Lewis) wrote: >> "Arthur J. O'Dwyer" <ajonos...@andrew.cmu.edu> writes in article <Pine.LNX.4.60-041.0608172202200.11...@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:
>>>>> 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.
On Wed, 23 Aug 2006, Arthur J. O'Dwyer wrote: > On Wed, 23 Aug 2006, Ed Murphy wrote: > > (Keith A. Lewis) wrote: > >> "Arthur J. O'Dwyer" <ajonos...@andrew.cmu.edu> writes > >>> On Fri, 18 Aug 2006, nobody wrote: > >>>> 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. ;-)
