Problem Analysis #21

To find the probability $p_5$ that three distinct points chosen uniformly at random from the 15 lattice points form a triangle, we first calculate the total number of ways to choose 3 points and then subtract the number of ways to choose 3 collinear points.

The total number of ways to choose 3 points from 15 is: $\binom{15}{3} = \frac{15 \times 14 \times 13}{3 \times 2 \times 1} = 455$

Next, we count the number of collinear sets of 3 points. Collinear sets can lie on vertical, horizontal, or diagonal lines.

1. Vertical lines: There are 3 vertical lines ($x=1, 2, 3$), each containing 5 points. The number of ways to choose 3 points from a vertical line is: $3 \times \binom{5}{3} = 3 \times 10 = 30$

2. Horizontal lines: There are 5 horizontal lines ($y=1, 2, 3, 4, 5$), each containing 3 points. The number of ways to choose 3 points from a horizontal line is: $5 \times \binom{3}{3} = 5 \times 1 = 5$

3. Diagonal lines: Since the grid has width 3, any diagonal line containing 3 points must have exactly one point on each of the vertical lines $x=1, x=2,$ and $x=3$. The $y$-coordinates of these points must form an arithmetic progression. The possible non-zero integer slopes $m$ for these lines are:

• For $m = 1$: 3 lines (starting at $y=1, 2, 3$)
• For $m = 2$: 1 line (starting at $y=1$)
• For $m = -1$: 3 lines (starting at $y=3, 4, 5$)
• For $m = -2$: 1 line (starting at $y=5$)

This gives a total of $3 + 1 + 3 + 1 = 8$ diagonal lines, each containing exactly 3 points. The number of ways to choose 3 points from these diagonal lines is: $8 \times \binom{3}{3} = 8$

Adding these up, the total number of collinear sets of 3 points is: $C = 30 + 5 + 8 = 43$

The number of sets of 3 points that form a triangle is: $455 - 43 = 412$

Thus, the probability $p_5$ is: $p_5 = \frac{412}{455}$

Since 412 = 2^2 $$\times$$ 103 and 455 = 5 $$\times$$ 7 $$\times$$ 13, the fraction is in lowest terms. We have $p = 412$ and $q = 455$.

Finally, we find $p + q$: $p + q = 412 + 455 = 867$

\boxed{867}