Problem Analysis #21

Total ways: C(15,3) = 455.

Count collinear triples.

Columns: x=3 columns each with 5 points: C(5,3)=10 each → 30. Rows: y=5 rows each with 3 points: C(3,3)=1 each → 5.

Diagonals and other lines.

Let me enumerate lines with ≥3 lattice points among the grid (3 wide, 5 tall).

Points: x in {1,2,3}, y in {1..5}.

Consider lines with various slopes.

Slope 0 (rows): done, 5 rows of 3 → 5 triples. Vertical: done, 30.

Now diagonal lines. Need at least 3 collinear points.

Slope 1: points (x,y) with y - x constant. Lines: for x=1,2,3. y-x values range.

• y-x = const, with x=1,2,3 giving y = c+1, c+2, c+3 all in 1..5. Need three points x=1,2,3 with y consecutive. y values: (1,2,3),(2,3,4),(3,4,5) → 3 lines, each 3 points → 3 triples.

Slope -1: y+x const. x=1,2,3, y decreasing. (x=1,y),(2,y-1),(3,y-2). Need y, y-1, y-2 in range with y from 3 to5 →3 lines → 3 triples.

Slope 1/2: change x by 2 changes y by 1. Points x=1,2,3 won't all be collinear unless... Actually with x spacing 1, slope 1/2 means between x=1 and x=2, y changes 0.5 — not integer. So need only points at x where y integer. Points at x=1 and x=3 with y differing by 1, midpoint x=2 y half-integer not lattice. So only 2 points max on such lines through grid? Let's check: slope 1/2 line passing through (1,1),(3,2): only those two lattice points in grid. No third.

Slope 2: between x=1,2: y changes 2; x=2,3 changes 2. So (1,y),(2,y+2),(3,y+4). Need y+4≤5 → y=1. Line (1,1),(2,3),(3,5): 3 points → 1 triple. Slope -2: (1,y),(2,y-2),(3,y-4): y=5 → (1,5),(2,3),(3,1): 1 triple.

Slope 1/2 lines using x=1 and 3 only (2 points) — no.

Other slopes with 3 points: need three collinear points. With only 3 x-values, a non-vertical line has at most 3 points (one per column). So count lines hitting all 3 columns with collinear integer y.

General: points (1,a),(2,b),(3,c) collinear iff b-a = c-b, i.e., a,b,c arithmetic. Count arithmetic progressions a,b,c in 1..5 with b = (a+c)/2.

So count triples (a,b,c) with a,c same parity, b = midpoint, all in 1..5. Number of (a,c) pairs (ordered as a<c or just compute): each valid arithmetic triple corresponds to choosing a and common difference d≠0 with a, a+d, a+2d in 1..5.

d=1: a from1to3 →3 (slope... gives differences in y =1, slope 1) — these are the slope-1 ones? Wait y=a,a+1,a+2 corresponds to slope 1. Yes 3. d=-1: a from3to5 →3 (slope -1). d=2: a=1 only → (1,3,5) slope 2. d=-2: a=5 → (5,3,1) slope -2.

Total: 3+3+1+1=8 triples that hit all three columns. These match what I found: 3+3+1+1=8.

So collinear triples through all 3 columns: 8.

Also lines within single column counted (30), rows (5).

Are there lines with 3 points all in two columns? No, 3 points collinear non-vertical need distinct x unless vertical. Two points per... can't have 3 collinear with only 2 distinct x unless vertical. So done.

Total collinear = 30 + 5 + 8 = 43.

Triangles = 455 - 43 = 412.

p5 = 412/455. GCD? 455 = 5·7·13. 412 = 4·103. No common factors.

p+q = 412+455 = 867.

\boxed{867}