## April 2011

This month, Gale Greenlee sent us a wonderful solution. We could not resist: and provide it here as is.

**“Boys and girls take warning, if you go near the lake
Keep your eyes wide open, and look for sneaky snake
Now maybe you won’t see him, maybe you won’t hear
But he’ll sneak up behind you, and drink all your root beer**

The first thing that comes to mind (my mind) is to count the ways the joints could bend when every one is a 90 degree turn to the left or right. Twenty segments, that’s nineteen joints.

One joint = two ways

Two joints = 4 ways

Three joints = 8 ways

Etc.

Etc.

But, in our puzzle the first joint is welded firmly with a 90 degree turn to the left. Then 18 more single type segments for a total of 19 solid pieces, or 18 joints that can go either left or right at 90 degree turns. So, 2^18= 262,144 ways or patterns.

We have one more restriction, just to make it fun. The snake can’t touch itself. So, we have to subtract, from the 262,144 number, the number of instances that have the snake touching itself. How in the world would we do that?

Let’s think about the very first thing that could go wrong. We could have the first choice available to us be a (L,L) followed by a (L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L). That would make a little box at the start of our pattern and foul the deal. So, that’s one of the bad patterns which we must subtract from the 262,144 number. What’s next. Well, - - - - - . But, wait there must be an easier way to do this.

Let’s subtract all the patterns that have any little four sided boxes in them in one fell swoop. In order to compute this number, I’m going to go at it backwards and compute all the total number of patterns that **DON’T** have at least one little box in them. That gets us there so to speak.

We have a neat trick available to us here. Our first joint after the welded head piece could be either (L) or (R). Two choices. The next joint after that has 3 choices etc. Study this and you will see:

Joint | Choices |
---|---|

1 | 2 |

2 | 3 |

3 | 5 |

4 | 8 |

5 | 13 |

6 | 21 |

7 | 34 |

8 | 55 |

9 | 89 |

10 | 144 |

11 | 233 |

12 | 377 |

13 | 610 |

14 | 987 |

15 | 1597 |

16 | 2584 |

17 | 4181 |

18 | 6765 |

We could subtract 6,765 from the 262,144 to calculate the 255,379 patterns that DO have little four sided boxes in them. It’s the **6,765** figure though that we were looking for.

That’s quite a trick. We are using the famous Fibonacci sequence here, where each succeeding number is the sum of the previous two. And 6,765 is the **20 ^{th}** one of these. Our snake, remember, has twenty segments, it’s just that the first two are welded together in a fixed left hand turn.

1 | 1 |
---|---|

2 | 1 |

3 | 2 |

4 | 3 |

5 | 3 |

6 | 8 |

7 | 13 |

8 | 21 |

9 | 34 |

10 | 55 |

11 | 89 |

12 | 144 |

13 | 233 |

14 | 377 |

15 | 610 |

16 | 987 |

17 | 1597 |

18 | 2584 |

19 | 4181 |

20 | 6765 |

This is great fun. I wish that were all there was too it. But, no! We have more problems.

Consider the joints (Lweld,L,R,L,L,R,L,L,R,L,L,R,R,L,R,L,R,L,R)

Or (Lweld,L,R,L,L,R,L,L,R,L,L,R L,L,R,L,L,R,L)

Here, in both cases, we don’t have any little four sided boxes, but the snake does touch itself.

**And then sneaky snake goes dancin’, wigglin’ and a-hissin’
Sneaky snake goes dancin’, gigglin’ and a-kissin’
I don’t like old sneaky snake; he laughs too much you see
When he goes wigglin’ through the grass, it tickles his underneath.**

If you draw out the two sequences above, you will see a twelve sided figure that closes. It looks like the red cross emblem. So, now we are worried about 12 sided figures that close, as opposed to 4 sided ones which we dealt with in the first part of this discussion.

Consider any of the twelve sided figures involved with the 20 segments. Think about those that lap over so to speak. We could have 8 segments on the head end lapping over or 8 segments on the tail end of the snake lapping over. Or, any combination of (8H,0T). (7H,1T),(6H,2T),(5H,3T),(4H,4T),(3H,5T),(2H,6T),(1H,7T) or (0H,8T).

.O-8 | 17 | 26 | 35 | 44 | 53 | 62 | 71 | 80 | .Sum | Product | |

1 | 55 | 55 | 55 | ||||||||

2 | 34 | 34 | 68 | ||||||||

3 | 21 | 21 | 63 | ||||||||

4 | 13 | 13 | 65 | ||||||||

8 | 8 | 8 | 64 | ||||||||

13 | 5 | 5 | 65 | ||||||||

21 | 3 | 3 | 63 | ||||||||

34 | 1 | 2 | 3 | 102 | |||||||

55 | 2 | 2 | 110 | ||||||||

655 |

Or, maybe this is really more appropriate:

.O-8 | 17 | 26 | 35 | 44 | 53 | 62 | 71 | 80 | .Sum | Product | |

1 | 55 | 55 | 55 | ||||||||

2 | 34 | 34 | 68 | ||||||||

3 | 21 | 21 | 63 | ||||||||

4 | 13 | 13 | 65 | ||||||||

8 | 8 | 8 | 64 | ||||||||

13 | 5 | 5 | 65 | ||||||||

21 | 3 | 3 | 63 | ||||||||

34 | 2 | 2 | 68 | ||||||||

55 | 1 | 1 | 55 | ||||||||

0 | 566 | ||||||||||

34 | 1 | 1 | 34 | ||||||||

55 | 1 | 1 | 55 | ||||||||

655 |

In any event I believe there are 655 patterns involving the closed 12 sided figure that must be subtracted from the 6,765.

**"Well, sneaky snake drinks root beer, and he just makes me sickWhen he is not dancin’, he looks just like a stickNow, he doesn’t have any arms or legs, you cannot see his earsAnd while we are not lookin’, he’s stealin’ all of our beer"**

Now we need to do the same kind of thing for the 16 sided figures and the four 20 sided figures.

Do I really have too? Yes! Here goes.

If you draw out the little 16 sided figure and study it awhile, you will see there are 8 positions available if you want to place the snake’s head right on the figure. Then there would be four tail segments lapping over in some manner. Of these 8 possibilities, two involve one choice only for the 17^{th} segment, while six allow two choices for the 17th segment. Remember now, four segments lapping over.

1……………………………….2

2……………………………….3

3……………………………….5

5……………………………….8

So, 2X5 plus 6X8 =**58** patterns when the snake’s head in right on the figure, or what we might call a (0H,4T) situation.

Now for the other lapping situations................

(1H,3T), (2H,2T), (3H,1T) and (4H,0T).

My count for each of these is 28,15,,24,and 18 totaling **85** patterns

This makes a total for the 16 figure problem equal to 58 plus 85 or **143**.

**"And then sneaky snake goes dancin’, wigglin’ and a-hissin’
Sneaky snake goes dancin’, gigglin’ and a-kissin’
I don’t like old sneaky snake; he laughs too much you see
When he goes wigglin’ through the grass, it tickles his underneath”**

Now for the famous 20 sided figures.

There are four patterns by my count and 5,10,10, and 20 possible positions for the snake’s head. So, **45** possible patterns.

So, in summary,

** 6765**

**-655**

**-143**

**-45**

**5922**

And 5922-26 equals the number of patents issued to IBM in the year 2010.

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com