Random triangles in a circle

[bonanova]

You've just found a neat way to place points uniformly randomly inside a unit circle: simply place points at random inside a circumscribed square -- x and y uniformly chosen on [-1, 1] -- and ignore the points near the square's corners that are outside the circle. There are other ways, but this works, and it's simple to do.

And why are you excited about this? The reason is that you've often wondered about the expected size of randomly drawn triangles inside a unit circle. And now you can find out. You sequentially place a million sets of three random points in the circle, calculating (and then averaging) the areas of the million triangles they define. And you find something pretty amazing: the million triangles had an average area that is only ~ 7.4% of the circle's area. You also note that the median area was ~ 5.4%.

OK, so that's a fairly long set-up for a pretty short puzzle. Read on.

You tell a friend about how amazingly small random triangles constrained by a circle are, and he replies with a question of his own: "That's cool," he says, "but I wonder what fraction of those triangles cover the circle's center?" You admit that was a piece of information that you did not take note of. "Oh, that's OK," your friend replies, "I think I can tell you."

What answer did your friend (correctly) come up with? 

[Molly Mae]

Let's think more generally.  Draw point A, the diameter containing A, point B, and its diameter (thanks, Iz!).  This is certainly the right path.

What is the expected area of the quadrant opposite these two points?  It can be as high as 1/2 (A, center, and B are colinear and found on the line in that order) or 0 (A, B, and center are colinear and found on the line in that order).  Those two (and all possibilities in between) occur randomly with equal probability.  The average of all them is 1/4.

If there's another (and better!) way to arrive at it, I'm sure Izzy can demonstrate it when she isn't busy. 

[flamebirde]

A thought:

Spoiler

The first two points (call them A and B) don't matter, since if you are able to choose the third one, it's always possible to choose one such that the center is within the triangle. (draw a line from the center of the line segment AB to the center, and then place the third point on the line at any point after it intersects the center.)

Hence, the question is only really about the third point.

More thoughts:

Spoiler

The farther you go on that line, the more tolerance you have for moving off it (i.e. when you've only gone one unit on the line, you might only be able to deviate .1 units off it, whereas if you go ten units you might be able to deviate by a full unit). Hence, the region where the third point needs to be placed is always within a certain sector of the circle.

 

[Izzy]

@Molly Mae, that doesn't quite work. You can draw some counter examples. It did give me a good idea, though. 

 

Spoiler

Arbitrarily draw points A and B. Then, draw two diameter lines,  one through the center and A, and the other through the center and B. Now, the circle is divided into four pieces, with opposite pieces being equal. The only way to form a triangle that goes through the center is either for point C to be on one of these diameter lines in the opposite quadrants of points A and B, or to be in the opposite quadrant of the quadrant between A and B. So, to calculate the probability is to calculate the area of that quadrant. 

I'm totally late to go teach my class, so I'll have to do that later. It does seem to be 1/4 though. 

 

[Izzy]

Spoiler

Place A anywhere. Draw the diameter through A and the center. Rotate this so that the line goes through (0,0) and (0,-1) on the Cartesian plane. 

Now, there is a 50% chance of placing B in the upper half of the circle, and a 50% chance of placing B in the lower half of the circle. 

If B is placed in the lower half of the circle, (without loss of generality, place B in the third quadrant), and draw a diameter between B and the center. Now, the possible places for C lie between the positive y-axis and the diameter we just drew. This piece ranges from having an area of 0 to pi/4. (I am assuming all such areas between 0 and pi/4 would occur with equal probability...) Then, on average, this piece has size which is 1/8 of the circle. 

If B is placed in the upper half of the circle, (without loss of generality, place B in the second quadrant), then again draw a diameter between B and the center. Now, the possible places for C lie between the positive y-axis and the diameter we just drew. (I am again assuming all such areas between 0 and pi/2 would occur with equal probability...). Then, on average, this piece has size which is 1/4 of the circle. 

So, we get 1/2*1/8 + 1/2*1/4 = 3/16, giving a 18.75% chance of drawing a triangle that passes through the center, slightly smaller than the 1/4 we got from eyeballing it. 

 

[plasmid]

Wait, did bonanova just say there’s a way to do it with a nasty integral?!?

Spoiler

Do like Izzy and Yuli. Let the angle between point A, the origin, and point B be θ, which will have uniform probability of being anything from 0 to π radians. The probability that point C will fall within the angle opposite θ and therefore have triangle ABC include the origin is simply θ/2π. So integrate that from 0 to π and divide by the size of the domain.

 

[bonanova]

Kudos to all. @flamebirde set up an attack framework, @Izzy got the puzzle to its knees, @Molly Mae knocked it out for the count and finally @plasmid, who just might have a penchant for shooting rabbits with elephant guns, put a bullet through its head.

To sort out the credits I'll don my judge's robes and presume to declare a verdict:

• @flamebirde told us it's all about angles. (Honorable mention. +1)
   
• @Molly Mae made four (equal) quadrants, which I have in my solution, and gave the right answer but didn't prove it, then switched to the @flamebirde - @Izzy model and backed up the answer with a word proof. (FTW)
   
• What must have been only moments later, @Izzy put numbers on things but, probably exhausted from her class, got the wrong number. (Honorable mention. +1)
   
• @plasmid dazzled us with calculus symbols and cold-blooded math to lay the newly-deceased puzzle to rest. (also Honorable mention, +1 but it doesn't seem enough. Timing is everything.)

As I followed your discussion, (credit to you all) it occurred to me that this might be the simplest non-math approach:

Spoiler

WOLOG place A on the -x axis, and B on any diameter, making the four sectors two of which, if they contain an arbitrary C, make triangles that cover the center with probabilities, (p and 1-p), just depending on which side of the origin B is. Since B can be either side of the origin with equal probability the value of p does not have to be considered -- only the average of p and 1-p.

 

[bonanova]

Hint:

Spoiler

As implied by the OP narrative, your friend did not need 1 million simulations. Just a little thought and a pencil and paper.

 

[Molly Mae]

1 hour ago, flamebirde said:

A thought:

  Hide contents

The first two points (call them A and B) don't matter, since if you are able to choose the third one, it's always possible to choose one such that the center is within the triangle. (draw a line from the center of the line segment AB to the center, and then place the third point on the line at any point after it intersects the center.)

Hence, the question is only really about the third point.

More thoughts:

  Hide contents

The farther you go on that line, the more tolerance you have for moving off it (i.e. when you've only gone one unit on the line, you might only be able to deviate .1 units off it, whereas if you go ten units you might be able to deviate by a full unit). Hence, the region where the third point needs to be placed is always within a certain sector of the circle.

 

Oh, nice start.

My answer is 1/4.  

Draw point A.  Then draw the diameter of the circle that passes through A and the centre.  This divides the circle into two distinct halves.  We can then draw a line perpendicular to this line to divide the circle into 4 equal parts.

Choose point B at random.  If point C is in the quadrant directly opposite point B, the cenre is inside the triangle.  Otherwise, it isn't.

Note: I disregard all subsets of points that are colinear.  I also include the centre as being "in" the triangle if it lies on an edge of the triangle.

[bonanova]

23 hours ago, Molly Mae said:

 

  Hide contents

My answer is 1/4.  

Draw point A.  Then draw the diameter of the circle that passes through A and the centre.  This divides the circle into two distinct halves.  We can then draw a line perpendicular to this line to divide the circle into 4 equal parts.

Choose point B at random.  If point C is in the quadrant directly opposite point B, the cenre is inside the triangle.  Otherwise, it isn't.

Note: I disregard all subsets of points that are colinear.  I also include the centre as being "in" the triangle if it lies on an edge of the triangle.

 

Spoiler

Recheck that.

 

@Molly Mae and @Izzy you both

Spoiler

have the beginnings of a proof. In both cases there is a (different) final question that needs to be answered, either by insight (yay) or evaluating an intergal (ugh)

 

[Molly Mae]

4 minutes ago, bonanova said:

  Hide contents

Recheck that.

 

Yowch.  Not only is that not true, but my initial premise isn't even correct.  In my mind, I couldn't draw one that wasn't.  Now, I can only think of counterexamples!

[Izzy]

Found the mistake! 

13 hours ago, Izzy said:

  Hide contents

Place A anywhere. Draw the diameter through A and the center. Rotate this so that the line goes through (0,0) and (0,-1) on the Cartesian plane. 

Now, there is a 50% chance of placing B in the upper half of the circle, and a 50% chance of placing B in the lower half of the circle. 

If B is placed in the lower half of the circle, (without loss of generality, place B in the third quadrant), and draw a diameter between B and the center. Now, the possible places for C lie between the positive y-axis and the diameter we just drew. This piece ranges from having an area of 0 to pi/4. (I am assuming all such areas between 0 and pi/4 would occur with equal probability...) Then, on average, this piece has size which is 1/8 of the circle. 

If B is placed in the upper half of the circle, (without loss of generality, place B in the second quadrant), then again draw a diameter between B and the center. Now, the possible places for C lie between the positive y-axis and the diameter we just drew. (I am again assuming all such areas between 0 and pi/2 would occur with equal probability...). Then, on average, this piece has size which is 1/4  3/8 of the circle (because it takes on values between 1/4 and 1/2 of the circle uniformly, not values between 0 and 1/2, whoops.) 

So, we get 1/2*1/8 + 1/2*1/4  3/8 = 1/4. 

 

 

[bonanova]

Yay!

And does it seem strange to anyone else that something 7% the size of the circle on average covers the center 25% of the time? (My red herring was soooo totally ignored. Good job for doing that.)