The four parachutists

[ceptimus]

Three parachutists land at random positions within a large circular cornfield. Albert fears that Barbara hurt herself on landing, so he dumps his gear and runs straight to her; but it turns out that she is fine, so he retraces his steps. Then both Albert and Barbara walk straight to Charlie, who happens to have landed closest to the field gate.

"The farmer will be annoyed", says Charlie, "Look at the triangle you've trodden out in his corn!"

Just then, Dennis, the first parachutist of the second drop, floats down into the field. If he lands in a random position, what are the chances that he will be inside the triangle?

[Sundog]

At first glance, there isn't enough info to solve the problem; there doesn't appear to be any clue as to the size of the field or its relation to the size of the triangle. Therefore I'm missing something, since I know you don't post unfair puzzles. Hmmm...

[Sundog]

Can we assume that the fourth skydiver left the plane at the exact point in the sky that the other three did?

edited to add: Not that that gets me very far either... :?

[Sundog]

Ceptimus! Wake up! I know it's the middle of the night there but that's no excuse.

[ceptimus]

A more boring way to state the problem, is:

Three points are placed at random within a circle. By random, I mean that equal areas within the circle have an equal chance of containing a point. What is the expected area of the triangle formed by the three points, as a fraction of the circle's area?

[Sundog]

That's what I was afraid you meant.

[Cecil]

Assume the field is a circle with radius 1, centered at (0,0). The area is then pi.

Albert lands at (r1, theta1), Barbara lands at (r2, theta2), and Charlie lands at (r3, theta3), where r1,r2,r3 are uniformly distributed variables over [0,1] and theta1, theta2, theta3 are UDVs over [0,2pi).

Let x1 = sqrt(r1)*cos(theta1) and y1 = sqrt(r1)*sin(theta1); similarly for x2,y2,x3,y3.

At this point the only way I see to finish is to solve a hell of a lot of ugly integrals. Any hints on an easier way?

[ceptimus]

Assume the field is a circle with radius 1, centered at (0,0). The area is then pi.

Albert lands at (r1, theta1), Barbara lands at (r2, theta2), and Charlie lands at (r3, theta3), where r1,r2,r3 are uniformly distributed variables over [0,1] and theta1, theta2, theta3 are UDVs over [0,2pi).

Let x1 = sqrt(r1)*cos(theta1) and y1 = sqrt(r1)*sin(theta1); similarly for x2,y2,x3,y3.

At this point the only way I see to finish is to solve a hell of a lot of ugly integrals. Any hints on an easier way?

The method you suggest won't give an even distribution of points - they will tend to cluster near the centre of the circle. If you are going to use polar coordinates, you'll need a non-uniform distribution of the radii to account for the fact that the area increases in proportion to the radius squared.

An alternative method is to use cartesian coordinates, and then the distributions on x and y are uniform. Of course, you have to deal with the boundary problem, as the field is circular, and not square. :)

Or you could do it the easy way. ;)

[Sundog]

Hmm. My math, trig and geometry are very rusty so please excuse me if I say something stupid. So maybe we can ignore the points themselves and say that the area of the triangle can itself vary randomly from zero to the maximum size of a triangle inscribed in the circle. If it's a linear distribution, or even a smooth function, that seems to give an answer. I can't take it further than that yet. Am I on the right track at all?

[DanishDynamite]

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

Google is a cool invention. :)

Still, I suspect there is a much easier way of solving this problem than the very hairy integrals given in the above link.

[Whim]

The largest triangle they could have created is an equilateral triangle that fits exactly inside the circle. From the math here, I say the odds are <= ~41.3%.

[Deetee]

These are the odds of him landing inside the triangle if it is the maximum allowable dimensions. The area of the inner triangle could approach zero, however, so the chance of the next jumper landing in the triangle varies from zero up to 41.3%
So to average out, is the chance 20.65% ?

[Cecil]

Assume the field is a circle with radius 1, centered at (0,0). The area is then pi.

Albert lands at (r1, theta1), Barbara lands at (r2, theta2), and Charlie lands at (r3, theta3), where r1,r2,r3 are uniformly distributed variables over [0,1] and theta1, theta2, theta3 are UDVs over [0,2pi).

Let x1 = sqrt(r1)*cos(theta1) and y1 = sqrt(r1)*sin(theta1); similarly for x2,y2,x3,y3.

At this point the only way I see to finish is to solve a hell of a lot of ugly integrals. Any hints on an easier way?

The method you suggest won't give an even distribution of points - they will tend to cluster near the centre of the circle. If you are going to use polar coordinates, you'll need a non-uniform distribution of the radii to account for the fact that the area increases in proportion to the radius squared.

Aye, that's why I used the sqrt(r) term above. I believe the formulae I gave for x1,y1 give an even distribution on a circle.

Or you could do it the easy way. ;)

*slaps forehead*

Of course, the easy way. Why didn't I think of that? :wink:

[ceptimus]

Oops! :oops:

Sorry Cecil, I missed the sqrt() function in your post. My bad.

I don't want to give too many hints till I see what others post.

[DanishDynamite]

So, ceptimus, when are you going to reveal the easy way to solve this one?

[ceptimus]

So, ceptimus, when are you going to reveal the easy way to solve this one?

You should know by now I always use computer programs whenever they are the easiest way:

Code: Select all

/*  numerical simulation of 'The four parachutists' puzzle posted on skepticalcommunity.com
 *  generate a random triangle inside a circle.  What is the probability that another random 
 *  point inside the circle is inside the triangle?
 */

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#include <time.h>

bool insideTriangle
(
    double x,  double y, 
    double x1, double y1,
    double x2, double y2,
    double x3, double y3
)
{
    double b;

    b =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    
    if ((((x2 - x) * (y3 - y) - (x3 - x) * (y2 - y)) / b) <= 0.0)
        return false;

    if ((((x3 - x) * (y1 - y) - (x1 - x) * (y3 - y)) / b) <= 0.0)
        return false;

    if ((((x1 - x) * (y2 - y) - (x2 - x) * (y1 - y)) / b) <= 0.0)
        return false;

    return true;
}

void randomPointInUnitCircle(double* x, double* y)
{
    do
    {
        *x = 2.0 * rand() / RAND_MAX - 1.0;
        *y = 2.0 * rand() / RAND_MAX - 1.0;
    } while (*x * *x + *y * *y > 1.0);
}

int get_key()
{
    int key = 0;

    if (kbhit())
        if ((key = getch()) == 0)
            key = -getch();

    return key;
}

int main(int argc, char* argv[])
{
    unsigned long trials = 0;
    unsigned long hits = 0;

    double x1, y1, x2, y2, x3, y3, x, y;

    int key;

    srand((unsigned)time(NULL));

    while (true)
    {
        randomPointInUnitCircle(&x1, &y1);
        randomPointInUnitCircle(&x2, &y2);
        randomPointInUnitCircle(&x3, &y3);
        randomPointInUnitCircle(&x,  &y);

        trials++;

        if (insideTriangle(x, y, x1, y1, x2, y2, x3, y3))
            hits++;

        if (!(trials % 100000))
        {
            printf("Trials:%9lu  Hits:%7.3f%%\n", trials, 100.0 * hits / trials);

            if ((key = get_key()) == 0X1B) // Esc
                exit(0);

            if (key == 'p') // pause
                while (!get_key())
                    ;
        }
    }

    return 0;
}

After a few minutes run time (it's been going while I prepared this post) the output looks like:

Code: Select all

Trials:794700000  Hits:  7.387%
Trials:794800000  Hits:  7.387%
Trials:794900000  Hits:  7.387%
Trials:795000000  Hits:  7.387%
Trials:795100000  Hits:  7.387%
Trials:795200000  Hits:  7.387%
Trials:795300000  Hits:  7.387%
Trials:795400000  Hits:  7.387%
Trials:795500000  Hits:  7.387%
Trials:795600000  Hits:  7.387%
Trials:795700000  Hits:  7.387%
Trials:795800000  Hits:  7.387%
Trials:795900000  Hits:  7.387%
Trials:796000000  Hits:  7.387%
Trials:796100000  Hits:  7.387%
Trials:796200000  Hits:  7.387%
Trials:796300000  Hits:  7.387%
Trials:796400000  Hits:  7.387%
Trials:796500000  Hits:  7.387%
Trials:796600000  Hits:  7.387%
Trials:796700000  Hits:  7.387%

I compared this result with the one from the mathworld link you provided - that link suggests the answer is 35 / (48 * PI^2) - and I found that it agrees pretty nearly.

[DanishDynamite]

So, ceptimus, when are you going to reveal the easy way to solve this one?

You should know by now I always use computer programs whenever they are the easiest way:

Code: Select all

/*  numerical simulation of 'The four parachutists' puzzle posted on skepticalcommunity.com
 *  generate a random triangle inside a circle.  What is the probability that another random 
 *  point inside the circle is inside the triangle?
 */

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#include <time.h>

bool insideTriangle
(
    double x,  double y, 
    double x1, double y1,
    double x2, double y2,
    double x3, double y3
)
{
    double b;

    b =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    
    if ((((x2 - x) * (y3 - y) - (x3 - x) * (y2 - y)) / b) <= 0.0)
        return false;

    if ((((x3 - x) * (y1 - y) - (x1 - x) * (y3 - y)) / b) <= 0.0)
        return false;

    if ((((x1 - x) * (y2 - y) - (x2 - x) * (y1 - y)) / b) <= 0.0)
        return false;

    return true;
}

void randomPointInUnitCircle(double* x, double* y)
{
    do
    {
        *x = 2.0 * rand() / RAND_MAX - 1.0;
        *y = 2.0 * rand() / RAND_MAX - 1.0;
    } while (*x * *x + *y * *y > 1.0);
}

int get_key()
{
    int key = 0;

    if (kbhit())
        if ((key = getch()) == 0)
            key = -getch();

    return key;
}

int main(int argc, char* argv[])
{
    unsigned long trials = 0;
    unsigned long hits = 0;

    double x1, y1, x2, y2, x3, y3, x, y;

    int key;

    srand((unsigned)time(NULL));

    while (true)
    {
        randomPointInUnitCircle(&x1, &y1);
        randomPointInUnitCircle(&x2, &y2);
        randomPointInUnitCircle(&x3, &y3);
        randomPointInUnitCircle(&x,  &y);

        trials++;

        if (insideTriangle(x, y, x1, y1, x2, y2, x3, y3))
            hits++;

        if (!(trials % 100000))
        {
            printf("Trials:%9lu  Hits:%7.3f%%\n", trials, 100.0 * hits / trials);

            if ((key = get_key()) == 0X1B) // Esc
                exit(0);

            if (key == 'p') // pause
                while (!get_key())
                    ;
        }
    }

    return 0;
}

After a few minutes run time (it's been going while I prepared this post) the output looks like:

Code: Select all

Trials:794700000  Hits:  7.387%
Trials:794800000  Hits:  7.387%
Trials:794900000  Hits:  7.387%
Trials:795000000  Hits:  7.387%
Trials:795100000  Hits:  7.387%
Trials:795200000  Hits:  7.387%
Trials:795300000  Hits:  7.387%
Trials:795400000  Hits:  7.387%
Trials:795500000  Hits:  7.387%
Trials:795600000  Hits:  7.387%
Trials:795700000  Hits:  7.387%
Trials:795800000  Hits:  7.387%
Trials:795900000  Hits:  7.387%
Trials:796000000  Hits:  7.387%
Trials:796100000  Hits:  7.387%
Trials:796200000  Hits:  7.387%
Trials:796300000  Hits:  7.387%
Trials:796400000  Hits:  7.387%
Trials:796500000  Hits:  7.387%
Trials:796600000  Hits:  7.387%
Trials:796700000  Hits:  7.387%

I compared this result with the one from the mathworld link you provided - that link suggests the answer is 35 / (48 * PI^2) - and I found that it agrees pretty nearly.

Thanks, ceptimus.

(You could have just said "I did a computer simulation". ) :)

[xouper]

Three parachutists land at random positions within a large circular cornfield. . . .

See, right away, you're off to a bad start since parachutists don't choose random landing spots. They choose to land where it will minimize the distance they have to walk back to the packing area.


:shock: :D :shock: :D

[Skeeve]

Three parachutists land at random positions within a large circular cornfield. . . .

See, right away, you're off to a bad start since parachutists don't choose random landing spots. They choose to land where it will minimize the distance they have to walk back to the packing area.


:shock: :D :shock: :D

Goodness me, perhaps I have been too hard on you, you're the first person to step back and see what the real problems with the question are. I seem to remember that Mel Frank told me that there was some way to derive the value of pi from some random kind of thing like this, although I thought it was dropping a pin. It has, I fear, been many years since I've had that conversation, would anyone remember what I should be able to remember here?

I'm not that much of a mathematics person. Although I did well enough in it, I greatly preferred rhetoric and natural languages.

[DanishDynamite]

Three parachutists land at random positions within a large circular cornfield. . . .

See, right away, you're off to a bad start since parachutists don't choose random landing spots. They choose to land where it will minimize the distance they have to walk back to the packing area.


:shock: :D :shock: :D

Goodness me, perhaps I have been too hard on you, you're the first person to step back and see what the real problems with the question are. I seem to remember that Mel Frank told me that there was some way to derive the value of pi from some random kind of thing like this, although I thought it was dropping a pin. It has, I fear, been many years since I've had that conversation, would anyone remember what I should be able to remember here?

I'm not that much of a mathematics person. Although I did well enough in it, I greatly preferred rhetoric and natural languages.

A quick google reveals this method:

Sample random points in a square, and count those that fall within a circle in the square. The ratio is proportional to the ratio of area of circle to a square.

From this ratio, you can derive Pi.