IBM Research | Ponder This | April 2011 solutions

# Ponder This

## April 2011

<<March April May>>

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
12
23
35
48
513
621
734
855
989
10144
11233
12377
13610
14987
151597
162584
174181
186765

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 20th 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.

11
21
32
43
53
68
713
821
934
1055
1189
12144
13233
14377
15610
16987
171597
182584
194181
206765

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).

  1 2 3 4 8 13 21 34 55 .O-8 17 26 35 44 53 62 71 80 .Sum Product 55 55 55 34 34 68 21 21 63 13 13 65 8 8 64 5 5 65 3 3 63 1 2 3 102 2 2 110 655

Or, maybe this is really more appropriate:

  1 2 3 4 8 13 21 34 55 .O-8 17 26 35 44 53 62 71 80 .Sum Product 55 55 55 34 34 68 21 21 63 13 13 65 8 8 64 5 5 65 3 3 63 2 2 68 1 1 55 0 566 1 1 34 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 sick
When he is not dancin’, he looks just like a stick
Now, he doesn’t have any arms or legs, you cannot see his ears
And 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 17th 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