All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Capture the Flag (Posted on 2008-05-04) Difficulty: 4 of 5

Let O designate the centre of an equilateral triangle. Points U-Z are chosen at random within the triangle. We have learnt that points U,V,W are each nearer to a (possibly different) vertex than to O; while X,Y are each closer to O than to any of the vertices.

Show that triangle XYZ is more likely than triangle UVW to contain the point O within its interior.

See The Solution Submitted by FrankM    
Rating: 3.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution semi-analytic; semi-computer | Comment 2 of 11 |

To demarcate the areas involved, divide each side of the equilateral triangle into 3 equal parts.  The points of division form a central regular hexagon inscribed within the triangle, leaving three small equilateral triangles, each with one of the original triangle's vertices as a vertex of its own.

The three points U,V and W are each located in one or another of the small vertex triangles.

If all three of the points U,V,W are within the same small triangle, the triangle they form cannot contain O.

If any two of the three are within the same small triangle, the probability is zero that the triangle formed would even include O on its perimeter. (That would be if one of the two points was at the vertex of the hexagon and the point not in the same small triangle were at the opposite vertex of the hexagon.)

That leaves the situation of each of the three points U,V,W being within a different one of the three small equilateral triangles. This has probability (2/3)*(1/3) = 2/9, and whenever this situation holds, O will be included within the formed triangle. There is probability zero that this will be on the perimeter of the formed triangle, occurring only if two of the points are as close together as possible while being in separate small triangles, and the third point is also at one of the two hexagon vertices that are on the remaining small triangle.

So the probability for U,V,W is 2/9.

The following program simulates the situation for X,Y,Z. The graphic statements, commented out via apostrophe, were for verifying where the points were being randomly placed. The iteration is done one million times, out of which, on 250,477 occasions, the formed triangle enclosed point O, strongly indicating the probability for X,Y,Z is 1/4, which is larger than that for U,V,W.

This is a modification from my program for Three Points in a Square.

DEFDBL A-Z
x0 = .5: y0 = SQR(3) / 6

'SCREEN 12

FOR i = 1 TO 1000000
  DO
   x1 = RND(1): y1 = RND(1)
  LOOP UNTIL y1 < SQR(3) / 3 AND y1 / x1 < SQR(3) AND y1 < SQR(3) * (1 - x1) AND y1 > SQR(3) * (1 / 3 - x1) AND y1 > SQR(3) * (x1 - 2 / 3)
  ' PSET (x1 * 400, (1 - y1) * 400), 12
  DO
   x2 = RND(1): y2 = RND(1)
  LOOP UNTIL y2 < SQR(3) / 3 AND y2 / x2 < SQR(3) AND y2 < SQR(3) * (1 - x2) AND y2 > SQR(3) * (1 / 3 - x2) AND y2 > SQR(3) * (x2 - 2 / 3)
  ' PSET (x2 * 400, (1 - y2) * 400), 14
  DO
   x3 = RND(1): y3 = RND(1)
  LOOP UNTIL y3 / x3 < SQR(3) AND y3 < SQR(3) * (1 - x3)
  ' PSET (x3 * 400, (1 - y3) * 400), 9
 
   m = (y2 - y1) / (x2 - x1)
   a = y1 - m * x1
   test1 = y3 - (m * x3 + a)
   test2 = y0 - (m * x0 + a)
  
   m = (y3 - y1) / (x3 - x1)
   a = y1 - m * x1
   test3 = y2 - (m * x2 + a)
   test4 = y0 - (m * x0 + a)
 
   m = (y3 - y2) / (x3 - x2)
   a = y2 - m * x2
   test5 = y1 - (m * x1 + a)
   test6 = y0 - (m * x0 + a)
 
   IF test1 * test2 > 0 AND test3 * test4 > 0 AND test5 * test6 > 0 THEN
     hit = hit + 1
   END IF
   ct = ct + 1
   PRINT hit, ct, hit / ct
NEXT

A variation of this program verifies the 2/9 probability found analytically, above, for U,V,W:

DEFDBL A-Z
x0 = .5: y0 = SQR(3) / 6

'SCREEN 12

FOR i = 1 TO 1000000
  DO
   x1 = RND(1): y1 = RND(1)
  LOOP UNTIL (y1 > SQR(3) / 3 OR y1 < SQR(3) * (1 / 3 - x1) OR y1 < SQR(3) * (x1 - 2 / 3)) AND y1 / x1 < SQR(3) AND y1 < SQR(3) * (1 - x1)
  ' PSET (x1 * 400, (1 - y1) * 400), 12
  DO
   x2 = RND(1): y2 = RND(1)
  LOOP UNTIL (y2 > SQR(3) / 3 OR y2 < SQR(3) * (1 / 3 - x2) OR y2 < SQR(3) * (x2 - 2 / 3)) AND y2 / x2 < SQR(3) AND y2 < SQR(3) * (1 - x2)
  ' PSET (x2 * 400, (1 - y2) * 400), 14
  DO
   x3 = RND(1): y3 = RND(1)
  LOOP UNTIL (y3 > SQR(3) / 3 OR y3 < SQR(3) * (1 / 3 - x3) OR y3 < SQR(3) * (x3 - 2 / 3)) AND y3 / x3 < SQR(3) AND y3 < SQR(3) * (1 - x3)
  ' PSET (x3 * 400, (1 - y3) * 400), 9
 
   m = (y2 - y1) / (x2 - x1)
   a = y1 - m * x1
   test1 = y3 - (m * x3 + a)
   test2 = y0 - (m * x0 + a)
  
   m = (y3 - y1) / (x3 - x1)
   a = y1 - m * x1
   test3 = y2 - (m * x2 + a)
   test4 = y0 - (m * x0 + a)
 
   m = (y3 - y2) / (x3 - x2)
   a = y2 - m * x2
   test5 = y1 - (m * x1 + a)
   test6 = y0 - (m * x0 + a)
 
   IF test1 * test2 > 0 AND test3 * test4 > 0 AND test5 * test6 > 0 THEN
     hit = hit + 1
   END IF
   ct = ct + 1
   PRINT hit, ct, hit / ct
NEXT

where the result was 222,234 occasions of U,V,W enclosing point O, out of a million sets of U,V,W; definitely close enough to the expected 222,222.22....

By the way, if the commented-out graphic statements are restored to activity, the program will not run under Windows Vista.  As of Vista, Microsoft has removed the capability of running DOS graphics programs. 

Edited on May 4, 2008, 6:29 pm
  Posted by Charlie on 2008-05-04 18:26:16

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information