Four darts

[bonanova]

This puzzle was discussed at length a few years ago in this forum.

It was rich enough that I thought it deserved another airing, with a largely

different set of puzzle solvers. I can't find it using search, to know for sure,

but I'm wondering whether Prime was one of the solvers last time.

For those to whom this is a new puzzle, I hope you will enjoy it.

It's simple to state, and challenging to solve.

I'm pretty poor at darts, but I managed to put three of them on the board.

Assuming my fourth dart also hits the board [circular], then

• what is the probability it will lie inside the triangle formed by the first three?
• what is the probability the four darts will not form a convex quadrilateral?

From the statement "I'm pretty poor at darts" you can assume that each dart

hits the board with a uniform probability of its x and y coordinates such that

x² + y² < 1

where r = 1 is the diameter of the board, and the coordinate origin is the center

of the board. Thus, if you simulate this, you can generate random points on a

double-unit square and discard points outside the unit circle -- the easiest way

to get uniform density inside a circle.

[Rob_Gandy]

My first thought when I read this was about areas. Given a triangle on a unit circle the probablility of a 4th point (dart) being in the triangle is (the area of the triangle)/Pi. The average area of a triangle in a unit circle is 35/(48Pi). So wouldn't that make the probablility of the 4th dart being in the triangle 35/(48Pi²) or approx. .07388? This is how I see this problem working in my mind.

[Prime]

I recall vaguely, trying to solve that problem. I seem to recall we did not come to a consensus back then. It seems like a serious math problem. And we were trying to solve only the question 2 there.

[Prime]

Since question 1 was not a part of that problem posted in 2008, let me provide a solution to that one real quick.

Let's say the probability of 4 darts forming a convex quadrilateral is

P.
Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

Proof:
Any convex quadrilateral forms a triangle with the 4th point inside, and from any triangle with a point inside 3 different quadrilaterals may be formed.
Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

Now, that question 1 is solved, I am inclined to yield the opportunity of solving question 2 to others.

Edited March 21, 2013 by Prime

[bushindo]

Since question 1 was not a part of that problem posted in 2008, let me provide a solution to that one real quick.

Let's say the probability of 4 darts forming a convex quadrilateral is

P.

Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

Proof:

Any convex quadrilateral forms a triangle with the 4th point inside, and from any triangle with a point inside 3 different quadrilaterals may be formed.

Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

Now, that question 1 is solved, I am inclined to yield the opportunity of solving question 2 to others.

I think the proof is fine as it is, but I believe there are a few typos. See below

Quoting Prime:

****************

Let's say the probability of 4 darts not forming a convex quadrilateral is P (i.e., P = probability the four darts form a triangle enclosing 1 point).

Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

Proof:

Any convex quadrilateral forms a triangle with the 4th point inside outside, and from any triangle with a point inside outside 3 different quadrilaterals may be formed.

Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

Question for bonanova: about question 1- the probability that the 4th point falls within the triangle,

So the problem is equivalent to finding the area of a triangle given 3 points, and then integrating that area over the distribution of those 3 points.

We need 2 coordinates to describe a single point in the circle, so we would need 6 coordinates (x₁, y₁, x₂, y₂, x₃, y₃) to describe any distribution of 3 points.

There is a straight forward formula for computing the area of a triangle given 3 points. As such, we can construct a sextuple integral for compute the solution. (Solving the integral analytically might be a problem, though the integral might be evaluated by numerical means)

I assume that such a sextuple integral is not acceptable as a solution =)?

[Prime]

Since question 1 was not a part of that problem posted in 2008, let me provide a solution to that one real quick.

Let's say the probability of 4 darts forming a convex quadrilateral is

P.

Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

Proof:

Any convex quadrilateral forms a triangle with the 4th point inside, and from any triangle with a point inside 3 different quadrilaterals may be formed.

Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

Now, that question 1 is solved, I am inclined to yield the opportunity of solving question 2 to others.

I think the proof is fine as it is, but I believe there are a few typos. See below

Quoting Prime:

****************

Let's say the probability of 4 darts not forming a convex quadrilateral is P (i.e., P = probability the four darts form a triangle enclosing 1 point).

Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

Proof:

Any convex quadrilateral forms a triangle with the 4th point inside outside, and from any triangle with a point inside outside 3 different quadrilaterals may be formed.

Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

Question for bonanova: about question 1- the probability that the 4th point falls within the triangle,

So the problem is equivalent to finding the area of a triangle given 3 points, and then integrating that area over the distribution of those 3 points.

We need 2 coordinates to describe a single point in the circle, so we would need 6 coordinates (x₁, y₁, x₂, y₂, x₃, y₃) to describe any distribution of 3 points.

There is a straight forward formula for computing the area of a triangle given 3 points. As such, we can construct a sextuple integral for compute the solution. (Solving the integral analytically might be a problem, though the integral might be evaluated by numerical means)

I assume that such a sextuple integral is not acceptable as a solution =)?

Yes, I muddled my explanation. Of course, I meant not forming convex quad, or forming concave quad. But I did mean the point inside a triangle. Perhaps, I should have mentioned re-drawing the lines connecting the points.

At any rate, my post solves the relation between question 1 and question 2.

The straightforward approach with sixtuple integral seems too complex and more a numeric than analytical solution. As far as I remember, Bonanova had done numeric solution back when, by runnig computer simulations.

[Prime]

My first thought when I read this was about areas. Given a triangle on a unit circle the probablility of a 4th point (dart) being in the triangle is (the area of the triangle)/Pi. The average area of a triangle in a unit circle is 35/(48Pi). So wouldn't that make the probablility of the 4th dart being in the triangle 35/(48Pi²) or approx. .07388? This is how I see this problem working in my mind.

If we know the average area of a randomly drawn triangle inside a unit circle, then the problem is solved. How do you find the average area of triangle? Where does 35/48Pi come from?

[Rob_Gandy]

My first thought when I read this was about areas. Given a triangle on a unit circle the probablility of a 4th point (dart) being in the triangle is (the area of the triangle)/Pi. The average area of a triangle in a unit circle is 35/(48Pi). So wouldn't that make the probablility of the 4th dart being in the triangle 35/(48Pi²) or approx. .07388? This is how I see this problem working in my mind.

If we know the average area of a randomly drawn triangle inside a unit circle, then the problem is solved. How do you find the average area of triangle? Where does 35/48Pi come from?

http://mathworld.wolfram.com/DiskTrianglePicking.html

[Prime]

The history of this problem as I recall it.

I suggested first solving the average distance between two points inside the unit circle. Then solving the average distance from a point to a segment inside the unit circle. Thus finding the average area of triangle and ultimately solving the problem.

I don't recall that anyone coming up with a solid analytical solution. Bonanova ran computer simulations providing the numeric answer and came up with analysis, which I did not quite follow at the time.

There was some confusion about the 4th point inside the triangle formed by the first 3 points, versus concave quadrilateral. I belive I resolved that question this time around in the post #3 with corrections by Bushindo in post #4.

[Prime]

My first thought when I read this was about areas. Given a triangle on a unit circle the probablility of a 4th point (dart) being in the triangle is (the area of the triangle)/Pi. The average area of a triangle in a unit circle is 35/(48Pi). So wouldn't that make the probablility of the 4th dart being in the triangle 35/(48Pi²) or approx. .07388? This is how I see this problem working in my mind.

If we know the average area of a randomly drawn triangle inside a unit circle, then the problem is solved. How do you find the average area of triangle? Where does 35/48Pi come from?

http://mathworld.wolfram.com/DiskTrianglePicking.html

But that's not solving the puzzle, that's finding an answer on the internet. I don't understand 5-tuple integrals and would have to study to verify that solution.

It is educational. However, to discover something of our own, I'd look for a simpler more understandable solution.

[bonanova]

The puzzle may have run its course. Probability is ratio of areas, and the triangle area is an hellacious multiple integral. The problem is known as Sylvester's four point problem.

I did find the number, as RG gave it, from simulation, not calculation. Uniform point-picking, necessary to form uniformly distributed triangles was an issue. Equally likely radius and angle gives preference to central points.

What was interesting to me when I simulated was that I was off by a factor of four that the four points would not be convex. That is, and should be 4 time the probability the 4th dart lands inside the triangle. There are three other areas the 4th dart can land that make a non-convex configuration, and those areas, on average, are equal to the triangle size. Not an intuitive result until you realize any of the darts can be taken to be the 4th dart.

So my last question now does not need to be asked, namely, to compare the probabilities of the two cases in the OP. also, that question has been answered in this thread.

Also, the mean triangle area was (to me) surprisingly small.

[bonanova]

Since question 1 was not a part of that problem posted in 2008, let me provide a solution to that one real quick.

Let's say the probability of 4 darts forming a convex quadrilateral is

P.

Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

Proof:

Any convex quadrilateral forms a triangle with the 4th point inside, and from any triangle with a point inside 3 different quadrilaterals may be formed.

Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

Now, that question 1 is solved, I am inclined to yield the opportunity of solving question 2 to others.

I think the proof is fine as it is, but I believe there are a few typos. See below

Quoting Prime:

****************

Let's say the probability of 4 darts not forming a convex quadrilateral is P (i.e., P = probability the four darts form a triangle enclosing 1 point).

Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

Proof:

Any convex quadrilateral forms a triangle with the 4th point inside outside, and from any triangle with a point inside outside 3 different quadrilaterals may be formed.

Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

Question for bonanova: about question 1- the probability that the 4th point falls within the triangle,

So the problem is equivalent to finding the area of a triangle given 3 points, and then integrating that area over the distribution of those 3 points.

We need 2 coordinates to describe a single point in the circle, so we would need 6 coordinates (x₁, y₁, x₂, y₂, x₃, y₃) to describe any distribution of 3 points.

There is a straight forward formula for computing the area of a triangle given 3 points. As such, we can construct a sextuple integral for compute the solution. (Solving the integral analytically might be a problem, though the integral might be evaluated by numerical means)

I assume that such a sextuple integral is not acceptable as a solution =)?

Tardy answering your question ... better late than never.

Sextuple integrals are indeed the solution. Nasty, but thankfully someone has already done it.