Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Permutations and Combinations
High School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/