Probability of Forming a Triangle

Date: 08/09/99 at 09:38:24
From: Sharon Lawson
Subject: Probability and Triangles

Hi,

I wonder if anybody can help me solve the following problem:

Three numbers are chosen from the first n natural numbers. What is the 
probability that they can be sides of a triangle? The numbers are 
picked "without replacement," so we cannot pick the same number twice.

I know that for this to be possible, the sum of any two sides must be 
greater than the third side, and obviously the sum of the three 
numbers cannot exceed 3*n - 3, but I don't know how to do it from 
there.

Thanks in advance for any help.
Sharon

Date: 08/09/99 at 18:47:36
From: Doctor Anthony
Subject: Re: Probability and Triangles

If the numbers range from 1 to n we can find a pattern for numbers 
that will form a triangle. In the pattern that I derive below, the 
case where the two shorter sides sum to give the longest side is 
included as a collapsed triangle. I give the two shorter sides first, 
then the longest side.

     1+2     - 3     2+3     - 4,5         3+4     - 5,6,7
     1+3     - 4     2+4     - 5,6         3+5     - 6,7,8
     1+4     - 5     2+5     - 6,7         3+6     - 7,8,9
      :        :      :         :           :          :
     1+(n-1) - n     2+(n-2) - (n-1),n     3+(n-3) - (n-2),(n-1),n
     ------------    2+(n-1) - n           3+(n-2) - (n-1),n
     Total = n-2     ------------------    3+(n-1) - n
                       Total = 2n-7        ------------------
                                            Total  = 3n-15

Continuing in this way we get the following series:

     (n-2), (2n-7), (3n-15), (4n-26), (5n-40), (6n-57), ...

The numbers in the brackets 2, 7, 15, 26, 40, 57, ... are given by:

     r(3r+1)/2   starting at r = 1

The end of the sequence is more complicated and we have different 
results depending on whether n is odd or even.

The top limit for r must be restricted to (n-1)/2 when n is odd and 
(n-2)/2 when n is even. Thereafter we have the sum of the triangular 
numbers up to the (n-3)/2 such number (for n odd) and the (n-2)/2 such 
number (for n even).

The triangular numbers are 1, 3, 6, 10, 15, 21, ... and the nth number 
is given by:

     n(n+1)/2

The sum of n terms of this triangular number series is given by:

       (1/2)SUM[n^2 + n]

     = (1/2)[n(n+1)(2n+1)/6 + n(n+1)/2]

     = (1/4)n(n+1)[(2n+1)/3 + 1]

     = (1/12)n(n+1)[2n+1+3]

     = (1/12)n(n+1)[2n+4]

     = (1/6)n(n+1)(n+2)

So the formula for the number of triangles will be, for n odd:

Let k = (n-1)/2

         k
        SUM[r.n - r(3r+1)/2] + (1/6)(k-1)k(k+1)
        r=1

         k
        SUM[r.n - r(3r+1)/2] + (1/6)k(k^2-1)
        r=1

And the formula for the number of triangles with n even:

Let k = (n-2)/2

         k
        SUM[r.n - r(3r+1)/2] + (1/6)k(k+1)(k+2)
        r=1 

Now you could choose 3 numbers from n numbers in C(n,3) ways, so the 
probability of forming a triangle, for n odd, is given by:

       k
      SUM[r.n - r(3r+1)/2] + (1/6)k(k^2-1)
      r=1
     --------------------------------------   where k = (n-1)/2
                     C(n,3)

and for n even the probability is:

       k
      SUM[r.n - r(3r+1)/2] + (1/6)k(k+1)(k+2)
      r=1
     -----------------------------------------   where k = (n-2)/2
                      C(n,3)


To avoid tedious algebra we shall work out this probability in the 
case where n = 20.

     k = (n-2)/2 = 9

The top line is:

        9
       SUM[20r - r(3r+1)/2] + (1/6)k(k+1)(k+2)   
       r=1 

     = 20.SUM[r) - (1/2)SUM[3r^2] - (1/2)SUM[r] +(1/6)(9)(10)(11) 

          for r = 1 to 9

     = 20(9)(10)/2 - (1/2)(3)(9)(10)(19)/6 - (1/2)(9)(10)/2 + 165

     = 900 - 427.5 - 22.5 + 165

     =  615

and C(20,3) = 1140

and so the required probability is  615/1140 = 41/76

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/