jump to navigation

USAMO 1973 #3 August 17, 2009

Posted by lumixedia in combinatorics, Problem-solving.
Tags: , , , ,
trackback

USAMO 1973 #3. Three distinct vertices are chosen at random from the vertices of a given regular polygon of {(2n+1)} sides. If all such choices are equally likely, what is the probability that the center of the given polygon lies in the interior of the triangle determined by the three chosen random points?

Solution. Fix the first chosen vertex. Suppose that if we move from vertex to vertex clockwise around the polygon starting from the first vertex, we land on the second vertex after {i} moves, {1\le i\le n}. Then there are {i} choices for the third vertex so that the triangle contains the center of the polygon. For example, if the second vertex is adjacent to the first, there is only one possible choice for the third vertex. If the second vertex is as far as possible from the first, reached after {n} moves, then any of the {n} vertices we haven’t moved to is a possible choice for the third vertex.

Of course, the same reasoning holds for choices of the second vertex so that we land on it after {i} counterclockwise moves starting from the first vertex, {1\le i\le n}. So we have {n} cases corresponding to the least number of moves from the first vertex to the second. The probability that there are {i} moves from the first vertex to the second is {\frac{2}{2n}=\frac{1}{n}}. Given that there are {i} moves from the first vertex to the second, the probability that the third vertex will satisfy the desired condition is {\frac{i}{2n-1}}. So the probability we want is

\displaystyle \sum_{i=1}^{n}\frac{1}{n}\cdot\frac{i}{2n-1}=\frac{1}{n(2n-1)}\cdot\frac{n(n+1)}{2}=\frac{n+1}{4n-2}

which is about {\frac{1}{4}} for large {n}.

Going beyond the problem in the obvious manner, we can make a similar calculation for a polygon with {2n} vertices. Now the second vertex can be {i} moves from the first vertex, {2\le i\le n-1}. (The center of the polygon will not lie in the interior of a triangle with two diametrically opposite vertices.) For each {i} there are {i-1} possible choices for the third vertex. Now the probability that the center of the polygon will lie in the interior of the triangle is

\displaystyle \sum_{i=2}^{n-1}\frac{1}{n}\cdot\frac{i-1}{2n-2}=\frac{1}{n(2n-2)}\cdot\frac{(n-2)(n-1)}{2}=\frac{n-2}{4n}

which is again about {\frac{1}{4}} for large {n}.

So the probability of the center of a circle lying in the interior of a triangle with vertices given by three random points on the circle really should be {\frac{1}{4}}. To my relief, this is true, from a standard geometric probability argument. Let {\alpha} be the clockwise angle from the first vertex to the second and {\beta} be the clockwise angle from the first vertex to the third. Both {\alpha} and {\beta} can vary from {0} to {2\pi}. If we graph {\beta} against {\alpha}, we see that the interval we can choose {\alpha} and {\beta} from is a square of side length {2\pi}. For {\alpha<\pi}, we need {\pi<\beta<\pi+\alpha} to satisfy the condition. For {\alpha>\pi}, we need {\alpha-\pi<\beta<\pi}. Shading in the appropriate areas on the graph, two triangular regions, it is easy to see that {\frac{1}{4}} of the square is shaded.

Finally, just for fun, the probability of the center of a {2n}-gon lying on the boundary of a triangle given by three random vertices of the {2n}-gon is {\frac{3}{n(2n-1)}}. We calculate this as follows. There are {\binom{2n}{3}} possible triangles. Of them {n(2n-2)} satisfy the desired condition, since there are {n} pairs of diametrically opposite vertices and {2n-2} choices for the third vertex for each pair. Dividing gives the answer.

…Okay, that was a lot longer than I planned to go on about a problem I’d put at the 15-20 range on a modern AMC-12. Heh.

About these ads

Comments»

1. Geometry and Probability problem | MathFax.com - August 9, 2010

[...] 6 : I’m sure 1/3 is correct. The problem is a particular case of problem 3 of the U.S.A. Mathematical Olympiad 1973. If the solution I’ve linked to were incorrect, a corrected solution would be easy to find, [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 43 other followers

%d bloggers like this: