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.

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search