Combinations of Pegs
Date: 02/04/97 at 11:19:42 From: Jamie Parnell Subject: Combinations On a square peg board there are sixteen pegs, four pegs to a side. If you connect any three pegs, how many triangles can you form? The answer in the book is 516, and the explanation is that you figure all possible combinations and then subtract those which result in a straight line. The closest I have gotten to the answer is 626 and I don't know any more combinations to take out.
Date: 02/04/97 at 15:14:25 From: Doctor Ken Subject: Re: Combinations Hi Jamie - I think your problem is not in finding how many combinations to take out, but in finding the first figure: all possible combinations of three pegs. There's a formula called the "choose" formula, and it says that if you want to find out how many ways you can choose 3 items from a set of 16 items, then the answer is: 16! 16*15*14 ---------- = ---------- = 8*5*14 = 560 3!(16-3)! 3*2*1 N! In general, N choose P is: --------- P!(N-P)! So since you're coming up with the number 626 after throwing out straight line combinations, that must be the part that's wrong. Let's look at why the "choose" formula works. If you're trying to choose three points from 16 points, how many ways can you choose the first point? You have 16 choices. How many ways for choosing the second point? There are 15 points left, so the number of ways of choosing the first two points is 16*15. For the third point, there are 14 choices left, so the number of different ways of choosing three points is 16*15*14. But wait a minute, we actually chose some triangles more than once! We have to throw away those duplicates. How many times did we count each triangle? Well, if the vertices of the triangle are A, B, and C, then we counted it in the following ways: ABC ACB BAC BCA CAB CBA That's 6 ways, and since we counted EVERY triangle 6 times, we can divide by 6. So we get 16*15*14/6, which is 16 choose 3. If you're interested in learning more about the choose formula and related things, you can look through our archives for topics like "combinations" and "permutations." I'll let you figure out the part where you have to throw away the combinations of three points that give you a straight line, since that's a little more visual. Good luck! -Doctor Ken, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum