Choosing Three Numbers from 1-10
Date: 06/08/2001 at 21:59:53 From: Craig Murai Subject: Permutations & combinations I am having difficulty solving the following 'combination' problem. Could you please explain your reasoning in solving the problem? Problem: How many ways can three numbers be chosen from the numbers 1,2,3,4,5,6,7,8,9,10 so that no two of the three numbers are consecutive? Answer: 56 Thanks!
Date: 06/09/2001 at 00:15:49 From: Doctor Schwa Subject: Re: Permutations & combinations Hi Craig, My first impulse is to think about the numbers that are *skipped* instead of the numbers that are chosen. That is, if the numbers that are chosen were 1, 3, and 8, then I'd represent that as 0142, the 0 meaning that no numbers are skipped at the beginning, then one number skipped after the 1, then four numbers skipped after the 3, then two numbers skipped after the 8. Since you chose three numbers out of 10, the four numbers you write have to add up to 7 (3 chosen leaves 7 to be skipped). The middle two numbers have to be at least 1. So, to make all four numbers be arbitrary (including 0 as legal), let's subtract one from each of the middle numbers. So now the choice of 1,3,8 would be written as 0032, where the total now is 5, and each of the four numbers can be anything (including 0). Another way to represent that, which makes it easier to count the number of ways to do it, is as , , xxx , xx where the commas separate the digits, and the x's tally the numbers. We know that there are a total of five x's and three commas, and they can go in any order, so there are (8 choose 3) which is 56 ways. For example, if you choose to put your x's and commas in order like xx , , x , xx that means 2012 in the later notation, but we have to add back the 1 in the middle, so that means 2122 are the number of skips, so decoding that, it means 3, 5, 8 are the numbers chosen. That's a pretty difficult way to get the answer, though, and I just figured out an easier way to do it. Because the answer I got last time was (8 choose 3), I thought it might make sense to choose any three numbers from 1 through 8 first, like say 1, 3, 4 Then insert one extra space to make sure there are no consecutive numbers (in other words, add 1 to the middle number and add 2 to the big number): 1, 4, 6 That will translate every set of three chosen from 8 into a set of nonconsecutives that are chosen from 10. Does that logic make sense? Please write back if it's not clear. Enjoy, - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.