No Two Consecutive Terms Divisible by 2 or 3

Date: 10/13/2002 at 21:40:26
From: Jon Thornton
Subject: Puzzle

In how many ways can numbers in the set {1,2,3,4,5,6} be ordered so 
that no two consecutive terms have a sum that is divisible by 2 or 3?

I've tried just guess and check but have had no luck. 

Thanks in advance,  
Jon

Date: 10/13/2002 at 22:04:59
From: Doctor Ian
Subject: Re: Puzzle

Hi Jon,

There are 6! (6 factorial, or 6*5*4*3*2*1) different orders that you 
could have. That's 720 possibilities, which is probably more than you 
want to check by hand.

But perhaps we can speed things up by seeing which pairs of numbers 
are divisible by 2 or 3. There are only 5+4+3+2+1, or 15 possible 
pairs:

  Pair   Sum   Div by 2 or 3? 
  ----   ---   --------------
  1,2     3       yes
  1,3     4       yes
  1,4     5       
  1,5     6       yes
  1,6     7       
  2,3     5       
  2,4     6       yes
  2,5     7
  2,6     8       yes
  3,4     7
  3,5     8       yes
  3,6     9       yes
  4,5     9       yes
  4,6    10       yes
  5,6    11

So the only pairs that _aren't_ divisible by 2 or 3 are

  Pair   Sum  
  ----   ---  
  1,4     5       
  1,6     7       
  2,3     5       
  2,5     7
  3,4     7
  5,6    11

So now it's just a matter of putting these pairs together so that 
the pairs at the boundaries are also members of this set, e.g., 

   These are both 'good' pairs
       __    __
      /  \  /  \
   ...1, 4, 3, 2,...
         \__/
                
    And so is this!
   
So this is a much smaller problem than the original one.  Can you 
finish up by yourself? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/