Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1973 USAMO Problems/Problem 3"

(→‎Solution)
m (The limit as n approaches infinity is 1/4, not 0)
 
(9 intermediate revisions by 5 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
There are <math>\binom{2n+1}{3}</math> ways how to pick the three vertices. We will now count the ways where the interior does NOT contain the center. These are obviously exactly the ways where all three picked vertices lie among some <math>n</math> consecutive vertices of the polygon.
+
There are <math>\binom{2n+1}{3}</math> ways how to pick the three vertices. We will now count the ways where the interior does NOT contain the center. These are obviously exactly the ways where all three picked vertices lie among some <math>n+1</math> consecutive vertices of the polygon.
−
We will count these as follows: We will go clockwise around the polygon. We can pick the first vertex arbitrarily (<math>2n+1</math> possibilities). Once we pick it, we have to pick <math>2</math> out of the next <math>n-1</math> vertices (<math>\binom{n-1}{2}</math> possibilities).
+
We will count these as follows: We will go clockwise around the polygon. We can pick the first vertex arbitrarily (<math>2n+1</math> possibilities). Once we pick it, we have to pick <math>2</math> out of the next <math>n</math> vertices (<math>\binom{n}{2}</math> possibilities).
  
 
Then the probability that our triangle does NOT contain the center is  
 
Then the probability that our triangle does NOT contain the center is  
Line 10: Line 10:
 
p
 
p
 
=
 
=
−
\frac{ (2n+1){\binom{n-1}{2}} }{ {\binom{2n+1}{3} } }
+
\frac{ (2n+1){\binom{n}{2}} }{ {\binom{2n+1}{3} } }
 
=
 
=
−
\frac{ (1/2)(2n+1)(n-1)(n-2) }{ (1/6)(2n+1)(2n)(2n-1) }
+
\frac{ (1/2)(2n+1)(n)(n-1) }{ (1/6)(2n+1)(2n)(2n-1) }
 
=  
 
=  
−
\frac{ 3(n-1)(n-2) }{ (2n)(2n-1) }
+
\frac{ 3(n)(n-1) }{ (2n)(2n-1) }
 
</cmath>
 
</cmath>
  
Line 21: Line 21:
 
1-p
 
1-p
 
=  
 
=  
−
\frac{ (2n)(2n-1) - 3(n-1)(n-2) }{ (2n)(2n-1) }
+
\frac{ (2n)(2n-1) - 3(n)(n-1) }{ (2n)(2n-1) }
 
=
 
=
−
\boxed{\frac{ n^2+7n-6 }{ 4n^2 - 2n }}
+
\frac{ n^2+n }{ 4n^2 - 2n }
 +
=
 +
\boxed{\frac{n+1}{4n-2}}
 +
 
 
</cmath>
 
</cmath>
−
Note: Trying the regular pentagon case, i.e n = 2, we get 12/12, or 1. The real probability is 1/2 for the pentagon, and the correct general formula is (n+1)/(4n-2).
+
== Perplexing Edge Case ==
 +
However, for <math>n = 1</math>, (a rare edge case), the circumcenter of the triangle must lie in the center of the triangle, which is notably difficult to prove if not assumed, resulting in a probability of <math>1</math>.
 +
 
 +
Observe that the probability tends to <math>\frac{1}{4}</math> as <math>n</math> approaches infinity. Why does this occur?
 +
 
 +
 
 +
{{alternate solutions}}
  
−
==See also==
+
==See Also==
  
 
{{USAMO box|year=1973|num-b=2|num-a=4}}
 
{{USAMO box|year=1973|num-b=2|num-a=4}}
 +
{{MAA Notice}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 07:32, 30 January 2023

Problem

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

There are $\binom{2n+1}{3}$ ways how to pick the three vertices. We will now count the ways where the interior does NOT contain the center. These are obviously exactly the ways where all three picked vertices lie among some $n+1$ consecutive vertices of the polygon. We will count these as follows: We will go clockwise around the polygon. We can pick the first vertex arbitrarily ($2n+1$ possibilities). Once we pick it, we have to pick $2$ out of the next $n$ vertices ($\binom{n}{2}$ possibilities).

Then the probability that our triangle does NOT contain the center is \[p = \frac{ (2n+1){\binom{n}{2}} }{ {\binom{2n+1}{3} } } = \frac{ (1/2)(2n+1)(n)(n-1) }{ (1/6)(2n+1)(2n)(2n-1) } = \frac{ 3(n)(n-1) }{ (2n)(2n-1) }\]

And then the probability we seek is \[1-p = \frac{ (2n)(2n-1) - 3(n)(n-1) }{ (2n)(2n-1) } = \frac{ n^2+n }{ 4n^2 - 2n } = \boxed{\frac{n+1}{4n-2}}\]

Perplexing Edge Case

However, for $n = 1$, (a rare edge case), the circumcenter of the triangle must lie in the center of the triangle, which is notably difficult to prove if not assumed, resulting in a probability of $1$.

Observe that the probability tends to $\frac{1}{4}$ as $n$ approaches infinity. Why does this occur?


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1973 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1973_USAMO_Problems/Problem_3&oldid=188382"