August 22, 2006

How many snakes on this plane?

Snakes are laid out on a plane with the following requirements:

  • Each snake has 3 parts: head, middle and tail.
  • Each snake is touched by exactly one head, one middle, and one tail.
  • Each snake can only touch another snake at most once.
  • Each part of a snake must touch a different part of another snake (no head-head, middle-middle, tail-tail).
  • The snakes can't overlap or cross as they are on a plane.

What is the minimum number of snakes that you need?

 

Posted by cedric at August 22, 2006 04:27 PM
Comments

I think it takes 8 snakes.

Posted by: Chris Nokleberg at August 22, 2006 06:26 PM

http://sixlegs.com/misc/snakes.png

You should wait until Friday to post these things you know :-)

Posted by: Chris Nokleberg at August 22, 2006 06:45 PM

Four.

Posted by: Alan Green at August 23, 2006 08:31 PM

I also say 4...

Posted by: Patrick Gras at August 25, 2006 03:30 AM

I was trying to find solutions to this puzzle because it was puzzling me elsewhere (that is, assuming the author intended to mention 0 is not a valid answer) and I stumbled upon this page.

By the way, Chris - your solution doesn't work. The third snake from the top (shaped like a '<') has two heads touching him.

Posted by: Mike M. at August 25, 2006 12:13 PM

zero

Posted by: Eugene Kaganovich at August 25, 2006 01:31 PM

zero

Posted by: Eugene Kaganovich at August 25, 2006 01:31 PM

Warez, lolitas, porn movies, cracks, trojans http://liveshow.ru

Posted by: Lolita at August 26, 2006 06:29 AM

Shoot!

Okay then I change my answer to infinity :-)

Posted by: Chris Nokleberg at August 26, 2006 09:16 AM

Zero is the easy way out. If you take zero then you miss out on some interesting problem solving.

After reading the rules it becomes immediately obvious there is only a small set of ways a snake can touch its neighbors. For any given snake, as soon as you touch its head to the tail of another you are forcing its middle to touch a head and tail to touch a middle. In fact there are exactly 2 ways for a snake to touch its neighbors.

http://img143.imageshack.us/img143/9196/snakesonaplanewo5.gif

Configuration #1 (C1) C1ís head touches a middle, C1ís middle touches a tail and C1ís tail touches a head.[a]

Configuration #2 (C2) C2ís head touches a tail, C2ís middle touches a head and C2ís tail touches a middle. [b]

The next thing to realize, as you begin to draw some C1 and C2 snakes on a plane, is that a C1 snake forces all snakes it touches into being C2. So by necessity, all C1 snakes must touch only C2 snakes and all C2 snakes must only touch C1 snakes. Also there must be and equal number of C1 and C2 snakes in order to prevent loose ends. This means that our solution (the minimum number of snakes) will need to be an even number.

With these observations letís begin drawing some snakes and see where it takes us. But instead of drawing some long snakes with heads and tails, lets just represent each snake as a box. Since all the snakes will be one of two types, and each snake must connect to a different type, weíll make some rows, each labeled either C1 or C2 and all the boxes that appear in a row will represent a snake with the labeled configuration. Then we can just draw a single line between boxes and weíll just assume that we can make head or tails of it later.

Since we are trying to find the minimum, lets start by placing a single snake in the first row C1 [c]. Based on what we know so far, we are going to need 3 snakes of type C2 that will connect to this first snake. Lets place all three in the next row and label it C2 and draw our lines to connect them.

Lets add a 3rd row (C1) and place one snake in it. Now we could connect this 5th snake to all three of the above [d]. If we did this the top-most and bottom-most snakes would be complete and all snakes in the middle row would be lacking exactly one touch. The problem is that we would be land-locking the middle snake with our lines. We havenít proved that this is a bad thing, but lets just assume it is and reject the idea of a single snake in the third row.

Instead lets add 2 snakes to the 3rd row completing the center snake [e]. We now have 3 C1 snakes and 3 C2 snakes, but 4 of these snakes are still missing one touch. We know that we need the same number of each kind, so lets add one of each, one in a 4th row and one in a 5th row [f]. And what do you know, they all link up nice and pretty.

All thatís needed now is to go through and replace each box with a head-middle-tail snake and link everything up according to the C1 and C2 rules. One possible result is the following[g].

Posted by: Mocky at August 28, 2006 12:46 PM

Zero is the easy way out. If you take zero then you miss out on some interesting problem solving.

After reading the rules it becomes immediately obvious there is only a small set of ways a snake can touch its neighbors. For any given snake, as soon as you touch its head to the tail of another you are forcing its middle to touch a head and tail to touch a middle. In fact there are exactly 2 ways for a snake to touch its neighbors.

http://img143.imageshack.us/img143/9196/snakesonaplanewo5.gif

Configuration #1 (C1) C1ís head touches a middle, C1ís middle touches a tail and C1ís tail touches a head.[a]

Configuration #2 (C2) C2ís head touches a tail, C2ís middle touches a head and C2ís tail touches a middle. [b]

The next thing to realize, as you begin to draw some C1 and C2 snakes on a plane, is that a C1 snake forces all snakes it touches into being C2. So by necessity, all C1 snakes must touch only C2 snakes and all C2 snakes must only touch C1 snakes. Also there must be and equal number of C1 and C2 snakes in order to prevent loose ends. This means that our solution (the minimum number of snakes) will need to be an even number.

With these observations letís begin drawing some snakes and see where it takes us. But instead of drawing some long snakes with heads and tails, lets just represent each snake as a box. Since all the snakes will be one of two types, and each snake must connect to a different type, weíll make some rows, each labeled either C1 or C2 and all the boxes that appear in a row will represent a snake with the labeled configuration. Then we can just draw a single line between boxes and weíll just assume that we can make head or tails of it later.

Since we are trying to find the minimum, lets start by placing a single snake in the first row C1 [c]. Based on what we know so far, we are going to need 3 snakes of type C2 that will connect to this first snake. Lets place all three in the next row and label it C2 and draw our lines to connect them.

Lets add a 3rd row (C1) and place one snake in it. Now we could connect this 5th snake to all three of the above [d]. If we did this the top-most and bottom-most snakes would be complete and all snakes in the middle row would be lacking exactly one touch. The problem is that we would be land-locking the middle snake with our lines. We havenít proved that this is a bad thing, but lets just assume it is and reject the idea of a single snake in the third row.

Instead lets add 2 snakes to the 3rd row completing the center snake [e]. We now have 3 C1 snakes and 3 C2 snakes, but 4 of these snakes are still missing one touch. We know that we need the same number of each kind, so lets add one of each, one in a 4th row and one in a 5th row [f]. And what do you know, they all link up nice and pretty.

All thatís needed now is to go through and replace each box with a head-middle-tail snake and link everything up according to the C1 and C2 rules. One possible result is the following[g].

Posted by: Mocky at August 28, 2006 12:47 PM

No really, Mocky, four.

Start off with two snakes 1 and 2. Have the tail of snake 1 (T1), touch the Head of snake 2 (H2). Now get snakes 3 and 4, with the head of 3 touching the tail of 4. That gives the following touching pairs:

T1 H2
H3 T4

At this stage, there are two free tails, two free heads and four free middles. If we match up the heads with the tails, that would leave four free middles, so instead, we match the heads and tails to the middles. Given the rules about only being able to touch each other snake once, there aren't many ways to do that. That gives the following additional pairs:

M1 T4
M2 H3
M3 T2
M4 H1

So that's all the pairs. You can then draw out the snakes on paper and satisfy yourself that the pairs can touch without the lines crossing.

Posted by: Alan Green at August 28, 2006 07:03 PM

That doesn't work Alan.

T1 H2
H3 T4

M1 T4
M2 H3
M3 T2
M4 H1

You omitted T3 and had T4 twice, so I assume that's a typo. You also omitted H4 and have H3 touching both T4 and M2.

But the bottom line with only 4 snakes even if you sort out your doubles and omissions is that you'll break rule #2 (Each snake is touched by exactly one head, one middle, and one tail.)

Posted by: Mocky at August 29, 2006 05:44 AM

Mocky,

Yeah, I think you're right. I fluffed it when I drew my picture.

Alan.

Posted by: Alan Green at September 4, 2006 05:35 PM
Post a comment






Remember personal info?