No Two Consecutive Terms Divisible by 2 or 3Date: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/