1
$\begingroup$

Twelve points in the plane are given, such that no three points are on the same line.

Five distinct segments joining pairs of these points are chosen at random, with all $\binom{12}{2} = 66$ such segments equally likely to be chosen. What is the probability that at least one triangle is formed by the chosen segments? (The triangle's three vertices must all come from the original set of 12 points.)

I know that we have to use PIE (because of the "at least") but I don't know how to start. Anyone want to help?

$\endgroup$
5
$\begingroup$

To choose five edges that make exactly one triangle, we need a triangle and we need an additional pair of edges that do not form a triangle with any of the other three edges. In one obvious way of counting successful choices of five edges, which is to count all the ways to choose one triangle and then choose two additional edges, we sometimes get more than one triangle, and these cases will be double-counted, so we do indeed have to use inclusion-exclusion, as you thought. (When we get only one triangle, the triangle and two non-triangle edges are not interchangeable, so there is no concern we have overcounted those cases.)

There is a one-to-one correspondence between triangles and sets of three points (where the three points are the vertices of the triangle). Picking three points from the $12$ possible vertices occurs $\binom{12}3$ ways, so

$$ \text{number of triangles} = \binom{12}3. $$

Given a triangle, there are $63$ edges remaining to choose from. We can choose two in any of $\binom{63}2$ ways. So for the first inclusion step of counting we have $$ \binom{12}3 \times \binom{63}2. $$

The only way to have two triangles from just five edges is to have exactly one shared edge and two other points, one for each of the other triangles (to use as the third vertex). There are $\binom{12}2$ possibilities for the shared edge, and from the $10$ remaining points we can choose the other two vertices in $\binom{10}2$ ways, so the number of possibilities to exclude in the first exclusion step is $$ \binom{12}2 \times \binom{10}2 . $$

There is no way to get more than two distinct triangles with just five edges, so we can stop here. There are $\binom{66}5$ equally-likely ways to choose five edges at random, so the final answer is

$$ p = \frac{\binom{12}3 \times \binom{63}2 - \binom{12}2 \times \binom{10}2}{\binom{66}5} \approx 0.04774459411556. $$

$\endgroup$
0
$\begingroup$

There are $ N = {66 \choose 5}$ choices of 5 edges. To form a triangle, I will need three edges to be $e_{01}, e_{12}, e_{20}$. The first triangle edge is a free choice (66 options), the second triangle edge has 11 options, and the final triangle edge has only 1 option.

We have $63 \times 62$ ways to choose the next two edges. The final two edges may form an additional triangle, but we only want to count those cases once. This only occurs when one of our edges is reused for the second triangle. This occurs ${3\choose 2}9 = 27 $ times for each first triangle we can choose (because there are 9 remaining points and we must use an edge between one of our original 3 points). In the end we have $M = 66 \times 11 \times 1 \times (63 \times 62 - 27)$ ways to form at least one triangle.

So $p = M/N \simeq .315 $.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm bad at counting so please double check my arguments :) $\endgroup$ – Dominic Reiss Nov 6 '19 at 22:21
  • $\begingroup$ It seems to me that you are entirely ignoring the problem of over-counting when a choice of edges results in two or more triangles. $\endgroup$ – TonyK Nov 6 '19 at 22:31
  • $\begingroup$ You're right of course. I will attempt to fix that. $\endgroup$ – Dominic Reiss Nov 6 '19 at 22:34
  • $\begingroup$ You have counted all the configurations that have two triangles twice, so you need to subtract them once. As you can't form three triangles, that is all you need. $\endgroup$ – Ross Millikan Nov 6 '19 at 22:38
  • 1
    $\begingroup$ @David The exact value is $\frac{\binom{12}{3}\binom{63}{2}-\frac{\binom{12}{3}\times 27}{2}}{\binom{66}{5}}$ which is $0.0477445941$ $\endgroup$ – Daniel Mathias Nov 9 '19 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.