Puzzle
12 minute read

Ponder This Challenge - April 2011 - How many snakes

Ponder This Challenge:

A wiggly plastic snake is composed of 20 segments. Assuming you start with a left turn, how many ways can the snake's other 18 joints be bent in 90-degree angles, either to the left or to the right, in such a way that the snake does not overlap/touch itself?

Thanks to Vi Hart for raising the question in her beautiful blog (link resides outside of ibm.com).

Bonus question: If you subtract the number of English letters from the answer, what is the connection of the result to the year 2010?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

  • 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:

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

    .O-81726354453627180.SumProduct
    1555555
    2343468
    3212163
    4131365
    88864
    135565
    213363
    34123102
    5522110
    655

    Or, maybe this is really more appropriate:

    .O-81726354453627180.SumProduct
    1555555
    2343468
    3212163
    4131365
    88864
    135565
    213363
    342268
    551155
    0566
    341134
    551155
    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.

Solvers

  • Daniel Bitin (04/01/2011 01:40 PM EDT)
  • Chidambaram Annamalai (04/01/2011 01:42 PM EDT)
  • Austin Shapiro (04/01/2011 03:01 PM EDT)
  • David Blackston (04/01/2011 03:58 PM EDT)
  • Joseph DeVincentis (04/01/2011 04:05 PM EDT)
  • Adam Daire (04/01/2011 05:17 PM EDT)
  • Shilei Zang (04/01/2011 05:48 PM EDT)
  • Tim Tran (04/01/2011 05:56 PM EDT)
  • Erik Postma (04/01/2011 06:30 PM EDT)
  • Motty Porat (04/01/2011 07:09 PM EDT)
  • Chuck Grant (04/01/2011 08:13 PM EDT)
  • Adam Hajari (04/01/2011 08:49 PM EDT)
  • Álvaro Begué (04/01/2011 09:25 PM EDT)
  • Victor Chang (04/01/2011 10:02 PM EDT)
  • Siyu Yang (04/01/2011 10:47 PM EDT)
  • Lu Wang (04/01/2011 11:33 PM EDT)
  • John T. Robinson (04/02/2011 12:00 AM EDT)
  • Nyles Heise (04/02/2011 12:19 AM EDT)
  • Mark Mixer (04/02/2011 06:51 AM EDT)
  • Emile Joubert (04/02/2011 08:48 AM EDT)
  • Federico de Ceballos (04/02/2011 02:21 PM EDT)
  • Chris Quayle (04/02/2011 02:38 PM EDT)
  • Matthew Paterson (04/02/2011 02:46 PM EDT)
  • Grant Stevens (04/02/2011 03:52 PM EDT)
  • Andrei Sipo (04/02/2011 04:12 PM EDT)
  • s (04/02/2011 04:12 PM EDT)
  • Balazs Ugron (04/02/2011 05:46 PM EDT)
  • Leif Jensen (04/02/2011 09:20 PM EDT)
  • Joshua Gunderson (04/02/2011 07:56 PM EDT)
  • Gary M. Gerken (04/02/2011 10:50 PM EDT)
  • Andreas Kabel (04/03/2011 04:35 AM EDT)
  • Nathanael Weldon (04/03/2011 06:01 AM EDT)
  • Piet Orye (04/03/2011 10:09 AM EDT)
  • Raúl Mora Pastor (04/03/2011 02:41 PM EDT)
  • Mathias Schenker (04/03/2011 04:01 PM EDT)
  • Harald van Dijk (04/03/2011 04:29 PM EDT)
  • Thijmen Krebs (04/03/2011 04:57 PM EDT)
  • Chris Shannon (04/03/2011 06:53 PM EDT)
  • Jonathan Campbell (04/03/2011 09:02 PM EDT)
  • Greg Janée (04/03/2011 09:03 PM EDT)
  • Rajendran Thirupugalsamy (04/03/2011 09:12 PM EDT)
  • Krunoslav Kovac (04/03/2011 11:51 PM EDT)
  • Blatter Christian (04/04/2011 09:54 AM EDT)
  • Mark Mammel (04/04/2011 12:59 PM EDT)
  • John Flavin (04/04/2011 02:33 PM EDT)
  • M. Zecevic (04/04/2011 02:46 PM EDT)
  • Phil Benamy (04/04/2011 03:09 PM EDT)
  • David Cole (04/04/2011 04:03 PM EDT)
  • Sandeep Rathour (04/04/2011 05:08 PM EDT)
  • James Wright (04/04/2011 05:59 PM EDT)
  • Matt Dobrin (04/04/2011 09:51 PM EDT)
  • Are Hjørungnes (04/04/2011 10:49 PM EDT)
  • Luke Pebody (04/05/2011 05:00 AM EDT)
  • Vincent Garnier (04/05/2011 07:20 AM EDT)
  • Panio Donev (04/05/2011 09:29 AM EDT)
  • Jonathon Noble Pendergrass (04/05/2011 12:02 PM EDT)
  • Dan Dima (04/05/2011 02:27 PM EDT)
  • David Friedman (04/05/2011 03:03 PM EDT)
  • Weichen Wang (04/05/2011 04:04 PM EDT)
  • Vitaly Ditman (04/06/2011 02:06 AM EDT)
  • Efthimios G. Karadimas (04/06/2011 08:02 AM EDT)
  • Miss Shawn Simpson (04/06/2011 03:44 PM EDT)
  • John Tromp (04/06/2011 08:13 PM EDT)
  • Anoop Ghanwani (04/06/2011 11:11 PM EDT)
  • John Duffield (04/07/2011 05:49 AM EDT)
  • Kurt Hectic (04/07/2011 07:14 AM EDT)
  • Danny Lynch (04/07/2011 09:02 AM EDT)
  • Benjamin Bachmann (04/07/2011 09:18 AM EDT)
  • Clive Tong (04/07/2011 02:22 PM EDT)
  • Jan Fricke (04/07/2011 04:30 PM EDT)
  • Sylvain Becker (04/07/2011 04:36 PM EDT)
  • Jamie Niemasik (04/07/2011 11:19 PM EDT)
  • Rick Kaye (04/08/2011 01:34 AM EDT)
  • David Gower (04/08/2011 11:25 AM EDT)
  • Donald T. Dodson (04/08/2011 01:06 PM EDT)
  • Armin Krauss (04/08/2011 02:50 PM EDT)
  • Vernon W. Miller (04/08/2011 08:17 PM EDT)
  • Sridivakar Inakonda (04/08/2011 10:57 PM EDT)
  • Andrea Andenna (04/09/2011 06:28 PM EDT)
  • William Heller (04/10/2011 11:16 AM EDT)
  • Sarthak Bagaria (04/10/2011 12:32 PM EDT)
  • John G. Fletcher (04/10/2011 07:52 PM EDT)
  • Stanislav Grudnitskiy (04/11/2011 12:35 AM EDT)
  • Jason Crease (04/11/2011 07:00 AM EDT)
  • Viacheslav Chernoy (04/11/2011 08:00 AM EDT)
  • Liubing Yu (04/12/2011 02:56 PM EDT)
  • Daniel Camero (04/12/2011 06:24 PM EDT)
  • Christian Pape (04/12/2011 06:39 PM EDT)
  • Bhavaji Sravani (04/12/2011 09:38 PM EDT)
  • Albert Stadler (04/13/2011 03:27 AM EDT)
  • Stéphane Higueret (04/13/2011 08:50 AM EDT)
  • Joe Riel (04/13/2011 12:43 PM EDT)
  • Ariel Flat (04/13/2011 03:10 PM EDT)
  • You Peijie (04/14/2011 10:00 AM EDT)
  • Gale Greenlee (04/15/2011 12:41 PM EDT)
  • Miguel Cuartas Hernández (04/15/2011 09:04 PM EDT)
  • Varun V. Vasista (04/16/2011 04:14 AM EDT)
  • Ehud Schreiber (04/17/2011 04:06 AM EDT)
  • Aliaksei Sanko (04/17/2011 09:27 AM EDT)
  • Sumanth Prabhu S (04/18/2011 02:37 PM EDT)
  • Phil Muhm (04/18/2011 02:48 PM EDT)
  • John Snyder (04/18/2011 04:46 PM EDT)
  • Javier Rodríguez (04/19/2011 11:01 AM EDT)
  • Amos Guler (04/20/2011 08:02 AM EDT)
  • Dustin Shively (04/20/2011 02:13 PM EDT)
  • Siddharth S. (04/22/2011 10:19 AM EDT)
  • Jens Koesling (04/25/2011 09:21 AM EDT)
  • Nick Vigo and Kipp Johnson (04/26/2011 10:06 AM EDT)
  • Robin Chandra (04/26/2011 10:38 AM EDT)
  • Henry Wong (04/26/2011 02:40 PM EDT)
  • Toncean Adrian (04/27/2011 04:43 AM EDT)
  • Taher Jamshidi & Arash Bahrami (04/27/2011 02:12 PM EDT)
  • Chuck Carroll (04/27/2011 09:46 PM EDT)
  • Mutaamba Maasha (04/28/2011 08:13 AM EDT)
  • Rafael Casado Sánchez (04/28/2011 10:59 PM EDT)
  • Vivek Nema (04/29/2011 02:59 AM EDT)
  • Fabio Michele Negroni (04/30/2011 03:50 PM EDT)
  • Ante Kovacic (04/30/2011 05:43 PM EDT)
  • Antonio García Astudillo (05/01/2011 08:58 AM EDT)

Related posts