2017 AMC 10A Problem 23

P21-25~8 minPrint

Basic Counting Paths & Grids Split into exhaustive cases and handle each Count the complement and subtract from the total

How many triangles with positive area have all their vertices at points $(i,j)$ in the coordinate plane, where $i$ and $j$ are integers between $1$ and $5$ , inclusive?

Show solution without answering

Key insight

Count all ways to pick 3 of the 25 points, then subtract picks lying on one line. Sort those lines by direction so none are missed.

Solution

Three points make a triangle unless they sit on one straight line. So count all groups of three points, then take away the groups that lie on a line.

1. All groups of three. There are $25$ points. The number of ways to choose $3$ of them is
$\frac{25 \times 24 \times 23}{3 \times 2 \times 1} = 2300.$
2. Groups on one line. A line through $5$ of the points holds $\frac{5 \times 4 \times 3}{6} = 10$ groups of three. A line through $4$ points holds $4$ groups. A line through exactly $3$ points holds $1$ . Now go through the directions a line can have.
3. Flat rows. $5$ rows, each with $5$ points: $5 \times 10 = 50$ .
4. Upright columns. Also $50$ .
5. Diagonals going up to the right. One long diagonal has $5$ points, two have $4$ , and two have $3$ (the shorter ones hold only $2$ or $1$ points). That gives $10 + 4 + 4 + 1 + 1 = 20$ .
6. Diagonals going down to the right. Same count by mirror symmetry: $20$ .
7. Lines that go $2$ across and $1$ up. Starting from a point, the next grid point on such a line is $2$ over and $1$ up. Three such points need $4$ columns of width, so they must use columns $1, 3, 5$ . Examples: $(1,1), (3,2), (5,3)$ , then $(1,2), (3,3), (5,4)$ , then $(1,3), (3,4), (5,5)$ . That is $3$ lines.
8. The other tilted directions. The same count works for $2$ across and $1$ down, $1$ across and $2$ up, and $1$ across and $2$ down (turn or flip the grid). Each gives $3$ lines, so all four together give $4 \times 3 = 12$ .
9. Steeper or flatter tilts. A line that goes $3$ across and $1$ up (or $3$ across and $2$ up, and so on) would need $6$ columns to reach a third point. The grid has only $5$ columns, so these give nothing. The same goes for the upright versions.
10. Total on lines: $50 + 50 + 20 + 20 + 12 = 152$ .
11. Triangles: $2300 - 152 = 2148$ .

The answer is $\boxed{\textbf{(B)}\ 2148}$ .

Why this works

When most choices work and a few fail, count everything and subtract the failures. The hard part is making sure the list of failures is complete. Sorting lines by their steps (across and up) and asking "can three points fit in the grid?" gives a checklist that catches the easy-to-miss tilted lines.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

There are $25$ lattice points, so $\binom{25}{3} = 2300$ ways to choose three of them. A choice fails to be a triangle exactly when the three points are collinear, so count collinear triples and subtract.

A line through the grid containing $k$ of the points contributes $\binom{k}{3}$ collinear triples. Go through the possible directions.

Horizontal: $5$ rows of $5$ points, $5 \cdot \binom{5}{3} = 50$ . Vertical: likewise $50$ .

Slope $\pm1$ : for each sign there is one diagonal with $5$ points, two with $4$ , and two with $3$ (shorter diagonals hold fewer than $3$ points). Per sign: $\binom{5}{3} + 2\binom{4}{3} + 2\binom{3}{3} = 10 + 8 + 2 = 20$ . Both signs: $40$ .

Slope $\pm2$ and $\pm\tfrac12$ : a line of slope $\tfrac12$ through lattice points steps $2$ right and $1$ up, so it can hold at most $3$ grid points, e.g. $(1,1), (3,2), (5,3)$ . For slope $\tfrac12$ the three points have $x = 1, 3, 5$ and $y = a, a+1, a+2$ with $a = 1, 2, 3$ : $3$ lines. By symmetry (reflect and swap axes) each of the four slopes $\pm2, \pm\tfrac12$ gives $3$ lines, for $12$ collinear triples.

Any other slope (such as $\tfrac13$ or $\tfrac23$ ) would need a horizontal or vertical span of at least $6$ to fit three lattice points, impossible here.

Collinear triples: $50 + 50 + 40 + 12 = 152$ . Triangles: $2300 - 152 = 2148$ .

The answer is $\boxed{\textbf{(B)}\ 2148}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.3)