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 "1999 AIME Problems/Problem 10"

(→‎Solution 2)
 
Line 2: Line 2:
 
Ten [[point]]s in the plane are given, with no three [[collinear]].  Four distinct [[segment]]s joining pairs of these points are chosen at random, all such segments being equally likely.  The [[probability]] that some three of the segments form a [[triangle]] whose vertices are among the ten given points is <math>m/n,</math> where <math>m_{}</math> and <math>n_{}</math> are [[relatively prime]] [[positive]] [[integer]]s.  Find <math>m+n.</math>
 
Ten [[point]]s in the plane are given, with no three [[collinear]].  Four distinct [[segment]]s joining pairs of these points are chosen at random, all such segments being equally likely.  The [[probability]] that some three of the segments form a [[triangle]] whose vertices are among the ten given points is <math>m/n,</math> where <math>m_{}</math> and <math>n_{}</math> are [[relatively prime]] [[positive]] [[integer]]s.  Find <math>m+n.</math>
  
−
== Solution ==
+
== Solution 1 ==
 
First, let us find the number of triangles that can be formed from the 10 points. Since none of the points are collinear, it is possible to pick <math>{10\choose3}</math> sets of 3 points which form triangles. However, a fourth distinct segment must also be picked. Since the triangle accounts for 3 segments, there are <math>45 - 3 = 42</math> segments remaining.
 
First, let us find the number of triangles that can be formed from the 10 points. Since none of the points are collinear, it is possible to pick <math>{10\choose3}</math> sets of 3 points which form triangles. However, a fourth distinct segment must also be picked. Since the triangle accounts for 3 segments, there are <math>45 - 3 = 42</math> segments remaining.
  
 
The total number of ways of picking four distinct segments is <math>{45\choose4}</math>. Thus, the requested probability is <math>\frac{{10\choose3} \cdot 42}{{45\choose4}} = \frac{10 \cdot 9 \cdot 8 \cdot 42 \cdot 4!}{45 \cdot 44 \cdot 43 \cdot 42 \cdot 3!} = \frac{16}{473}</math>. The solution is <math>m + n = 489</math>.
 
The total number of ways of picking four distinct segments is <math>{45\choose4}</math>. Thus, the requested probability is <math>\frac{{10\choose3} \cdot 42}{{45\choose4}} = \frac{10 \cdot 9 \cdot 8 \cdot 42 \cdot 4!}{45 \cdot 44 \cdot 43 \cdot 42 \cdot 3!} = \frac{16}{473}</math>. The solution is <math>m + n = 489</math>.
  
−
=== Solution 2 ===
+
== Solution 2 ==
 
Note that 4 points can NEVER form 2 triangles. Therefore, we just need to multiply the probability that the first three segments picked form a triangle by 4. We can pick any segment for the first choice, then only segments that share an endpoint with the first one, then the one segment that completes the triangle. Note that the fourth segment doesn't matter in this case.
 
Note that 4 points can NEVER form 2 triangles. Therefore, we just need to multiply the probability that the first three segments picked form a triangle by 4. We can pick any segment for the first choice, then only segments that share an endpoint with the first one, then the one segment that completes the triangle. Note that the fourth segment doesn't matter in this case.
 
Note that there are <math>(9 - 1) \times 2 = 16</math> segments that share an endpoint with the first segment. The answer is then <math>4 \times \frac{16}{44} \times \frac{1}{43} = \frac{16}{11} \times \frac{1}{43} = \frac{16}{473} \implies m + n = \boxed{489}</math>
 
Note that there are <math>(9 - 1) \times 2 = 16</math> segments that share an endpoint with the first segment. The answer is then <math>4 \times \frac{16}{44} \times \frac{1}{43} = \frac{16}{11} \times \frac{1}{43} = \frac{16}{473} \implies m + n = \boxed{489}</math>
 
-whatRthose
 
-whatRthose
  
 +
== Solution 3 ==
 +
Instead of working with the four segments, let's focus on their endpoints. When we select these segments, we are working with <math>4, 5, 6, 7,</math> or <math>8</math> endpoints in total.
 +
 +
If we have <math>6, 7,</math> or <math>8</math> endpoints, it is easy to see that we cannot form a triangle by drawing four segments between them, because at least one point will be "left out".
 +
 +
However, if we have <math>5</math> endpoints, we can use three segments form a triangle with three of the points and connect the remaining two points with the last segment. There are <math>{10\choose5}</math> ways to select these <math>5</math> points from the original <math>10,</math> and <math>{5\choose3}</math> ways to decide which three points are in the triangle.
 +
 +
Finally, if we have <math>4</math> endpoints, we can also form a triangle with three of the points, then use the remaining segment to connect the last point to either of the previous three. We have <math>{10\choose4}</math> ways to select the <math>4</math> points and <math>{4\choose3}</math> ways to choose three points for the triangle. Finally, we must connect the last point to one vertex of the triangle; we can do this in <math>3</math> ways.
 +
 +
As in Solution 1, there are <math>{45\choose4}</math> total ways to select four segments. So, our desired probability is
 +
 +
<cmath>\dfrac{{10\choose5}{5\choose3}+{10\choose4}{4\choose3}\cdot 3}{{45\choose4}}=\dfrac{16}{473} \implies m + n = \boxed{489}.</cmath>
 +
 +
--vaporwave
 
== See also ==
 
== See also ==
 
{{AIME box|year=1999|num-b=9|num-a=11}}
 
{{AIME box|year=1999|num-b=9|num-a=11}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 17:25, 17 July 2023

Problem

Ten points in the plane are given, with no three collinear. Four distinct segments joining pairs of these points are chosen at random, all such segments being equally likely. The probability that some three of the segments form a triangle whose vertices are among the ten given points is $m/n,$ where $m_{}$ and $n_{}$ are relatively prime positive integers. Find $m+n.$

Solution 1

First, let us find the number of triangles that can be formed from the 10 points. Since none of the points are collinear, it is possible to pick ${10\choose3}$ sets of 3 points which form triangles. However, a fourth distinct segment must also be picked. Since the triangle accounts for 3 segments, there are $45 - 3 = 42$ segments remaining.

The total number of ways of picking four distinct segments is ${45\choose4}$. Thus, the requested probability is $\frac{{10\choose3} \cdot 42}{{45\choose4}} = \frac{10 \cdot 9 \cdot 8 \cdot 42 \cdot 4!}{45 \cdot 44 \cdot 43 \cdot 42 \cdot 3!} = \frac{16}{473}$. The solution is $m + n = 489$.

Solution 2

Note that 4 points can NEVER form 2 triangles. Therefore, we just need to multiply the probability that the first three segments picked form a triangle by 4. We can pick any segment for the first choice, then only segments that share an endpoint with the first one, then the one segment that completes the triangle. Note that the fourth segment doesn't matter in this case. Note that there are $(9 - 1) \times 2 = 16$ segments that share an endpoint with the first segment. The answer is then $4 \times \frac{16}{44} \times \frac{1}{43} = \frac{16}{11} \times \frac{1}{43} = \frac{16}{473} \implies m + n = \boxed{489}$ -whatRthose

Solution 3

Instead of working with the four segments, let's focus on their endpoints. When we select these segments, we are working with $4, 5, 6, 7,$ or $8$ endpoints in total.

If we have $6, 7,$ or $8$ endpoints, it is easy to see that we cannot form a triangle by drawing four segments between them, because at least one point will be "left out".

However, if we have $5$ endpoints, we can use three segments form a triangle with three of the points and connect the remaining two points with the last segment. There are ${10\choose5}$ ways to select these $5$ points from the original $10,$ and ${5\choose3}$ ways to decide which three points are in the triangle.

Finally, if we have $4$ endpoints, we can also form a triangle with three of the points, then use the remaining segment to connect the last point to either of the previous three. We have ${10\choose4}$ ways to select the $4$ points and ${4\choose3}$ ways to choose three points for the triangle. Finally, we must connect the last point to one vertex of the triangle; we can do this in $3$ ways.

As in Solution 1, there are ${45\choose4}$ total ways to select four segments. So, our desired probability is

\[\dfrac{{10\choose5}{5\choose3}+{10\choose4}{4\choose3}\cdot 3}{{45\choose4}}=\dfrac{16}{473} \implies m + n = \boxed{489}.\]

--vaporwave

See also

1999 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=1999_AIME_Problems/Problem_10&oldid=195834"