Ponder This Challenge - March 2006 - Expected area of random triangle

Ponder This Challenge:

Puzzle for March 2006.

Consider 3 points chosen at random in an unit square. These points form a triangle. We want to compute the expected (average) area of this triangle. This can be done by answering the following questions.

1. Consider the minimum rectangle (with edges parallel to the edges of the unit square), R, containing the 3 random points. On average what is the area of R?

2. Given R, there are two configurations of the three points
   which occur with positive probability. They are

Case A - 2 points at opposite corners of R, remaining point in the
interior of R.

Case B - 1 point at a corner of R, 1 point along each of the 2 edges of R opposite the corner.

Show that the probabilities of occurrence of these two cases are independent of R. What are these probabilities?

3. What is the expected fraction of the area of R which is inside the triangle for each of the cases A and B above?

4. Combining the answers to questions 1-3, what is the expected area of the triangle formed by three points chosen at random in an unit square?

As usual we ask that you only submit your original work.

The first 100 people who answer all 4 parts correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Answer:

  We give the answers with a sketch of the proofs. We assume the unit square lies in the x-y plane with corners (0,0),(0,1), (1,1) and (1,0).

  1. .25. R is bounded by the minimum and maximum x and y coordinates of the 3 random points. It is well known and easy to prove that the minimum of the 3 random numbers chosen in the unit interval has average value .25. Similarly the maximum has average value .75. So on average the distance between opposite sides of R is .5. Since the x and y coordinates of the points are chosen independently this means the average area of R is .25.

  2. 1/3, 2/3. Let the sides of R have lengths a and b. For case A we have 2 choices for the diagonally opposite corners and the third point can occur anywhere in R so we have 2 degrees of freedom and area element 2*a*b. For case B we have 4 choices for the corner element with the remaining 2 points lying along line segments of length a and b. So again we have 2 degrees of freedom and area element 4*a*b. So case B is twice as likely as case A. Other configurations have fewer degrees of freedom hence occur with probability 0. So case A occurs with probability 1/3 and case B occurs with probability 2/3.

  Alternatively as pointed out by several solvers note R is determined by the values of the x and y coordinates while the case is determined by how the x and y coordinates are paired together with case A occurring when the middle x coordinate is
  paired with the middle y coordinate which will occur 1/3 of the time.

  3. Case A - 1/6. Here the third point will lie in a triangle (determined by 3 corners of R) of area .5*R. It will divide this triangle into 3 triangles having equal area on average (by symmetry). So the area of the triangle including two opposite corners of R will average R/6.

  Case B - 3/8. Here the triangle is what is left after triangles containing the 3 other corners of R are removed. The triangles containing the adjacent corners of R have average area R/4. The triangle containing the opposite corner of R has average area R/8. Hence the remaining triangular area in the middle determined by the 3 points has average area (3/8)*R.

  4. 11/144. The computation is (1/4)*((1/3)*(1/6)+(2/3)*(3/8)) =(1/4)((1/18)+(1/4))=(1/4)*(11/36)=11/144.

  This problem is closely related to Sylvester's four-point problem (1865) which asks for the probability that the convex hull of 4 points chosen at random is a quadrilateral (as opposed to a triangle). The first solution is attributed to Woolhouse (1867). I came up with the above derivation myself but it seems doubtful it is original. And in fact as a reader points out it can be found on the internet attributed to Robert Dawson.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Roberto Tauraso (03.01.2006 @11:58:25 AM EDT)
• Joseph DeVincentis (03.01.2006 @01:41:26 PM EDT)
• William C Hasenplaugh (03.01.2006 @03:50:13 PM EDT)
• Balakrishnan V (03.01.2006 @06:21:05 PM EDT)
• Arthur Breitman (03.01.2006 @07:31:40 PM EDT)
• Aditya Mahajan (03.01.2006 @05:53:20 PM EDT)
• Yurun Liu (03.01.2006 @10:04:39 PM EDT)
• Jing Shan (03.02.2006 @12:30:56 AM EDT)
• Frank Yang (03.02.2006 @12:54:56 AM EDT)
• Lukas Saul (03.02.2006 @01:53:17 AM EDT)
• Malcolm J. Powell (03.02.2006 @12:43:38 PM EDT)
• Michael Swart (03.02.2006 @01:15:27 PM EDT)
• Greg Bubnis (03.02.2006 @01:46:41 PM EDT)
• Frank Mullin (03.02.2006 @02:29:45 PM EDT)
• Dan Dima (03.03.2006 @03:03:29 AM EDT)
• Se Kwon Kim (03.03.2006 @10:18:06 AM EDT)
• Manuel Gräf (03.03.2006 @10:29:45 AM EDT)
• John G. Fletcher (03.03.2006 @01:55:09 PM EDT)
• aman_cc (03.03.2006 @05:18:41 PM EDT)
• Lovro Puzar (03.03.2006 @06:20:58 PM EDT)
• Graeme McRae (03.03.2006 @08:45:53 PM EDT)
• John Dalbec (03.04.2006 @12:24:06 AM EDT)
• Sandeep Rathour (03.04.2006 @01:36:33 AM EDT)
• Jacques Willekens (03.04.2006 @05:40:41 AM EDT)
• Allan Lazarovici (03.04.2006 @02:26:31 PM EDT)
• Chris Messer (03.05.2006 @05:09:27 PM EDT)
• David McQuillan (03.05.2006 @06:49:07 PM EDT)
• James Dow Allen (03.05.2006 @11:57:47 PM EDT)
• Gaurav Agrawal (03.06.2006 @01:37:53 AM EDT)
• Ed Sheppard (03.06.2006 @11:28:43 AM EDT)
• Phil Muhm (03.06.2006 @10:22:03 PM EDT)
• Vance Berger and Brendan Berger (03.07.2006 @12:41:54 PM EDT)
• David Friedman (03.08.2006 @11:01:17 AM EDT)
• Bill Schwennicke (03.08.2006 @05:42:01 PM EDT)
• Vincent Vermaut (03.09.2006 @02:34:38 AM EDT)
• David Wang (03.09.2006 @12:09:08 PM EDT)
• Rajkumar Pal (03.09.2006 @07:18:31 PM EDT)
• Zhou Guang (03.09.2006 @08:02:16 PM EDT)
• Manikandan Jagadeesan (03.10.2006 @02:08:46 PM EDT)
• Mark Pilloff (03.10.2006 @06:02:50 PM EDT)
• Wolf Mosle (03.11.2006 @07:36:58 PM EDT)
• John Ritson (03.11.2006 @11:19:27 PM EDT)
• Aliekber Gurel (03.12.2006 @01:32:04 AM EDT)
• Dion K Harmon (03.12.2006 @11:01:32 AM EDT)
• Joaquim N. Carrapa (03.12.2006 @08:31:45 PM EDT)
• Pascal Zimmer (03.13.2006 @06:33:15 PM EDT)
• Rubén Hernández Aza (03.13.2006 @10:48:40 PM EDT)
• Immanuel Litzroth (03.14.2006 @10:29:50 AM EDT)
• Evgeny (03.14.2006 @10:22:59 PM EDT)
• Ariel Flat (03.15.2006 @03:25:28 PM EDT)
• Michael Szydlo (03.15.2006 @03:44:07 PM EDT)
• Job Philip (03.17.2006 @06:55:45 AM EDT)
• Du Yang (03.17.2006 @10:05:11 PM EDT)
• Kennan Shelton (03.20.2006 @10:19:15 PM EDT)
• Adel El-Atawy (03.20.2006 @11:33:58 PM EDT)
• Harinarayanan E V (03.21.2006 @06:20:52 AM EDT)
• Alexey Vorobyov (03.22.2006 @07:46:41 PM EDT)
• Tom Sirgedas (03.23.2006 @11:59:35 AM EDT)
• Ranchu Mathew (03.23.2006 @12:09:48 PM EDT)
• Mahmoud Elhaddad (03.24.2006 @11:37:55 PM EDT)
• Amin Ahmad (03.27.2006 @02:57:36 AM EDT)
• Daniel Chong Jyh Tar (03.27.2006 @08:15:49 PM EDT)
• Dmytry Lavrov (03.28.2006 @05:43:37 PM EDT)