wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Triangles
        
(Message started by: Johno-G on Jan 18^th, 2003, 10:34am)

Title: Triangles
Post by Johno-G on Jan 18^th, 2003, 10:34am

n straight lines are drawn, such that the following three rules hold true:
a) all lines are drawn in the same plane,
b) no two lines are parallel to each other, and
c) no more than two lines intersect at any given point on the plane.

In total, how many triangles can be drawn using these n lines?

Title: Re: Triangles
Post by Garzahd on Jan 20^th, 2003, 3:27pm

>(n choose 3), or (n(n-1)(n-2)/6).<

Following the usual principles of "how did you solve that?", I'll try an explanation for those who have never taken a combinatorics class:

The key insight is for each set of 3 lines you select, they'll form a triangle.

So how many sets are there? Well, we have n choices of our first line, (n-1) choices for the second line, and (n-2) choices for the third line. By multiplying these together, we have a count of the number of triangles... but we end up counting each triangle six times, because for any set of three sides, we could get the order as ABC, ABC, BAC, BCA, CAB, CBA and think of them as different triangles. So the final answer is (n(n-1)(n-2)/6).

In combinatorics, mechanisms like this are generalized as follows: To describe the number of ways k items can be selected from n choices, they use the term (n choose k), which can be mathematically expanded as n!/(k!)((n-k)!)

Nontrivial combinatorics can get rather interesting, as it can make simple solutions to problems like "X pirates are trying to divide Y gold bars amongst each other, not necessarily evenly. How many ways can it be divided?"