From Newsgroup: rec.puzzles
James Dow Allen <
user4353@newsgrouper.org.invalid> posted:
(I don't think these classics have appeared in r.p before.)
Question:
Place four points randomly in the interior of a parallelogram.
What is the probability that the four points can be ordered to achieve
a convex quadrilateral?
The answer and its proof follow a poem provided as spoiler warning space.
============= 60 lines of SPOILER WARNING space follow ============ ============= 59 lines of SPOILER WARNING space follow ============ ============= 58 lines of SPOILER WARNING space follow ============
The first of a Phantom's Fyve Rules from Phantasmagoria, by Lewis Carroll
(Provided for the use of anyone anywhere at no cost and with
almost no restrictions whatsoever. You may copy it, give it away or
re-use it under the terms at www.gutenberg.org.)
. rCLMY FirstrCobut donrCOt suppose,rCY he said,
. . rCLIrCOm setting you a riddlerCo
. IsrCoif your Victim be in bed,
. DonrCOt touch the curtains at his head,
. . But take them in the middle,
. rCLAnd wave them slowly in and out,
. . While drawing them asunder;
. And in a minuterCOs time, no doubt,
. HerCOll raise his head and look about
. . With eyes of wrath and wonder.
. rCLAnd here you must on no pretence
. . Make the first observation.
. Wait for the Victim to commence:
. No Ghost of any common sense
. . Begins a conversation.
. [Picture: Ghostly border] rCLIf he should say rCy_How came you here_?rCO
. . (The way that _you_ began, Sir,)
. In such a case your course is clearrCo
. rCy_On the batrCOs back_, _my little dear_!rCO
. . Is the appropriate answer.
. rCLIf after this he says no more,
. . YourCOd best perhaps curtail your
. ExertionsrCogo and shake the door,
. And then, if he begins to snore,
. . YourCOll know the thingrCOs a failure.
. rCLBy day, if he should be alonerCo
. . At home or on a walkrCo
. You merely give a hollow groan,
. To indicate the kind of tone
. . In which you mean to talk.
. rCLBut if you find him with his friends,
. . The thing is rather harder.
. In such a case success depends
. On picking up some candle-ends,
. . Or butter, in the larder.
. rCLWith this you make a kind of slide
. . (It answers best with suet),
. On which you must contrive to glide,
. And swing yourself from side to siderCo
. . One soon learns how to do it.
============= END OF SPOILER WARNING ============
============= END OF SPOILER WARNING ============
============= END OF SPOILER WARNING ============
============= END OF SPOILER WARNING ============
Place four points randomly in the interior of a parallelogram.
What is the probability that the four points can be ordered to achieve
a convex quadrilateral?
The desired probability is 25/36. Proof follows.
The proof will use
. . the properties of affine transforms
. . the identity Mean(f(x)) = f(Mean(x)) when f() is linear.
We will first derive the area of a random triangle in the interior
of a parallelogram of unit area.
1. Facts about affine transforms mean that we can replace the parallelogram with a square, and align the sides of the square along x- and y-axes.
The corners of the square have (x,y) coordinates (0,0) : (0,1) : (1,1) : (1,0).
1b. We will place three points in the interior of that square and derive the area of the triangle they form. (From there the quadrilateral convexity probability will quickly follow.)
2. Place N-1 points randomly on the segment (0,1). The mean location of
the left-most point will be 1/N. Proof: Obviously true if the perimeter
of a circle is used instead of a line segment. Simple snip out
the first point placed on the circle. and (2) follows at once.
3. Name the three random points from left-most to right-most as A, B, C.
From (2), the mean x-coordinates of A and C are respectively 1/4 and 3/4. Because all that follows has the simple linear behavior desired we can
fix those x-coordinates to be the constants 1/4 and 3/4 by the mean/linear identity.
4. Similarly the top-most and bottom-most among A, B, C will have y-coordinates 3/4 and 1/4. We need never worry about two points sharing the same
coordinate: This occurs with probability zero and thus can be ignored.
5. All three of the points thus lie on or in a rectangle of mean area 1/4. Using affine transforms we convert this back to the (0,0)-(0,1)-(1,1)-(1,0) square, remembering to divide areas by 4 at the end.
6. One point resides at one of the square's corners. Where are the other two points?
Without loss of generality we need consider only two cases.
7. One-third of the time point B (whose x-coordinate is between those
of A and C) will also be the middle point when y-coordinates are considered.
In this ("difficult") case the three coordinate pairs will be (without loss of generality) (0,1), (1,0) and (x,y) where x+y < 1.
8. Two-thirds of the time (and without loss of generality) the three points will be (1,1), (x,0) and (0,y). Draw this and see the unit square has been divided
into 4 triangles with areas (1-x)/2, (1-y)/2, xy/2, and the target whose area we seek.
The area of the target triangle is therefore 1 - (1-x)/2 - (1-y)/2 - xy/2,
or (x+y-xy)/2.
9. Doing a double integral, each over [0,1] of (x+y-xy)/2 produces 3/8.
This is the same number achieved by the usual "Mean/linear" trick of substituting
the means x=1/2, y=1/2. This despite that the product xy can introduce non-linearity.
That the lower bounds of x and y are zero may explain this serendipity,
but details are left to the reader. The integration is simple enough.
10. So 2/3 of the time, the triangle's area averages 3/8. Let's complete
the calculation with the "difficult" case described in (7).
11. If you don't mind, let's double the triangle's area and divide by 2 at
the end. Thus we seek the mean area of a triangle whose base is 2 and whose altitude varies from 0 to 1. But the pdf isn't constant; it's maximal when altitude is 0 and disappears at 1. That pdf is given by 2-2h, where h is the altitude; (2h)/2 is the triangle's area. Integrate (2-2h)(h) from
0 to 1. The integral is (h^2 - 2h^3/3) and the definite integral (1 - 2/3).
We divide by 2 as promised and finish with 1/6.
12. At last! The mean area of the triangle sought in (4) is the
sum of (2/3)(3/8) from (10) and (1/3)(1/6) from (11). Let's divide by 4
as promised in (4), so the mean area of the triangle sought in (1a) is (2/12)(3/8) + (1/12)(1/6) = 11/144.
13. That's a nice result, but not what we were originally asked for.
We want the probability that FOUR random points in the parallelogram's
interior will form a convex quadrilateral.
14. Starting with the 3 points A,B,C whose triangular area we just found (11/144), produce a 4th random point D. D lies in the interior of the ABC triangle with probability 11/144. When this happens the quadrilateral ABCD cannot be convex.
15. Similarly C lies in the interior of ABD also with probability 11/144; and so on for B in ACD and A in BCD. These events are mutually exclusive so
the combined chance of any such "failure" is 4*11/144.
16. ABCD will form a CONCAVE quadrilateral if and only if one of the 4 "failures"
in (15) occurs. the probability that ABCD can be ordered to form a
convex quadrilateral is therefore 1 - 4*(11/144) = 25/36.
17. Q
18. E
19 D
Cheers, Gmail @ JamesDowAllen
--- Synchronet 3.22a-Linux NewsLink 1.2