The four parachutists

Stump your fellow simians.
User avatar
ceptimus
Posts: 1084
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Has thanked: 56 times
Been thanked: 41 times

The four parachutists

Post by ceptimus » Tue Jul 20, 2004 4:23 pm

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?

User avatar
Sundog
Posts: 2576
Joined: Mon Jun 07, 2004 4:27 pm

Post by Sundog » Tue Jul 20, 2004 5:15 pm

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...

User avatar
Sundog
Posts: 2576
Joined: Mon Jun 07, 2004 4:27 pm

Post by Sundog » Tue Jul 20, 2004 9:56 pm

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... :?
Last edited by Sundog on Tue Jul 20, 2004 10:42 pm, edited 1 time in total.

User avatar
Sundog
Posts: 2576
Joined: Mon Jun 07, 2004 4:27 pm

Post by Sundog » Tue Jul 20, 2004 10:38 pm

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

User avatar
ceptimus
Posts: 1084
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Has thanked: 56 times
Been thanked: 41 times

Post by ceptimus » Wed Jul 21, 2004 10:30 am

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?

User avatar
Sundog
Posts: 2576
Joined: Mon Jun 07, 2004 4:27 pm

Post by Sundog » Wed Jul 21, 2004 2:25 pm

That's what I was afraid you meant.

User avatar
Cecil
Posts: 131
Joined: Thu Jun 10, 2004 9:14 pm
Location: Vancouver
Been thanked: 1 time

Post by Cecil » Wed Jul 21, 2004 4:47 pm

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?

User avatar
ceptimus
Posts: 1084
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Has thanked: 56 times
Been thanked: 41 times

Post by ceptimus » Wed Jul 21, 2004 5:33 pm

Cecil wrote: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. ;)

User avatar
Sundog
Posts: 2576
Joined: Mon Jun 07, 2004 4:27 pm

Post by Sundog » Wed Jul 21, 2004 6:45 pm

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?
Last edited by Sundog on Wed Jul 21, 2004 7:14 pm, edited 1 time in total.

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite » Wed Jul 21, 2004 7:08 pm

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
Posts: 6
Joined: Wed Jul 07, 2004 10:25 pm

Post by Whim » Wed Jul 21, 2004 10:09 pm

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%.

User avatar
Deetee
Posts: 12
Joined: Fri Jul 09, 2004 5:31 pm
Location: Jupiter's moons

Post by Deetee » Thu Jul 22, 2004 5:30 pm

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% ?

User avatar
Cecil
Posts: 131
Joined: Thu Jun 10, 2004 9:14 pm
Location: Vancouver
Been thanked: 1 time

Post by Cecil » Fri Jul 23, 2004 8:51 pm

ceptimus wrote:
Cecil wrote: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:

User avatar
ceptimus
Posts: 1084
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Has thanked: 56 times
Been thanked: 41 times

Post by ceptimus » Fri Jul 23, 2004 10:11 pm

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.

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite » Mon Aug 09, 2004 3:17 pm

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

User avatar
ceptimus
Posts: 1084
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Has thanked: 56 times
Been thanked: 41 times

Post by ceptimus » Tue Aug 10, 2004 10:45 am

DanishDynamite wrote: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.

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite » Tue Aug 10, 2004 9:34 pm

ceptimus wrote:
DanishDynamite wrote: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". ) :)

User avatar
xouper
Posts: 8968
Joined: Fri Jun 11, 2004 4:52 am
Location: HockeyTown USA
Has thanked: 238 times
Been thanked: 144 times

Re: The four parachutists

Post by xouper » Wed Aug 11, 2004 6:18 pm

ceptimus wrote: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

User avatar
Skeeve
Posts: 10555
Joined: Wed Jun 09, 2004 7:35 am
Has thanked: 69 times
Been thanked: 83 times

Re: The four parachutists

Post by Skeeve » Wed Aug 11, 2004 6:26 pm

xouper wrote:
ceptimus wrote: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.
Then Skank Of America could start in...

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Re: The four parachutists

Post by DanishDynamite » Wed Aug 11, 2004 6:32 pm

Skeeve wrote:
xouper wrote:
ceptimus wrote: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.