Problem Analysis #21

The total number of lattice points is $15$. Choosing 3 points gives $\binom{15}{3} = 455$ total triplets. A triangle is formed if the three points are not collinear.

Collinear triplets occur on:

• Horizontal lines: 5 lines, each with 3 points → 5 triplets.
• Vertical lines: 3 lines, each with 5 points → $3 \times \binom{5}{3} = 30$ triplets.
• Diagonal lines: any non-vertical, non-horizontal collinear triplet must have $x$-coordinates $1,2,3$; the $y$-coordinates form an arithmetic progression with difference $d$ such that all $y$ values lie in $1,\dots,5$.
  • $d=1$: $y=1,2,3$; $2,3,4$; $3,4,5$ → 3 lines.
  • $d=-1$: $y=5,4,3$; $4,3,2$; $3,2,1$ → 3 lines.
  • $d=2$: $y=1,3,5$ → 1 line.
  • $d=-2$: $y=5,3,1$ → 1 line.
    Total diagonal triplets = 8.

Total collinear triplets = $5 + 30 + 8 = 43$.
Probability of a triangle = $1 - \frac{43}{455} = \frac{412}{455}$.
Since $412$ and $455$ are coprime, $p=412$, $q=455$, and $p+q=867$.

\boxed{867}