AMC 10 · 2005 · #12

Grade 8 number-theory

Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Grid Diagonal Cell Count

coordinate-geometrygcddivisibility-rules convert-to-algebrasystematic-enumeration ↑ Prerequisites: slope-interceptgcdfraction-arithmetic

📏 Medium solution 💡 2 insights

Problem

A straight line joins the points one, one and one hundred, one thousand. Count the points on the segment strictly between them whose coordinates are both whole numbers.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Introduce a Variable

Sliding the whole picture so that A lands on the origin costs nothing (both coordinates move by whole numbers, so integer points stay integer points) and makes the line equation as simple as possible. Then naming the running x-coordinate as a variable turns the geometric question "is this point a lattice point?" into a plain divisibility question about one integer, which can be answered exactly rather than by scanning a picture.

1STEP 1

Slide A to the origin

A whole-number shift moves one endpoint to the origin without changing the count.

(x,y)↦(x-1, y-1), A(1,1)↦(0,0), B(100,1000)↦(99,999)

2STEP 2

Reduce the slope

The slope reduces, and only the reduced form matters.

m=(1000-1)/(100-1)=999/99=111/11, gcd(111,11)=1

3STEP 3

Turn lattice point into divisibility

Being a lattice point then becomes one divisibility condition.

y=111x/11inZ⇔ 11 ∣ 111x⇔ 11 ∣ x

4STEP 4

List the multiples of 11

Listing the multiples inside the range gives 8 points.

x∈{11,22,33,44,55,66,77,88} → 8 points, e.g. (12,112),…,(89,889) in the original frame

5STEP 5

Cross-check with the gcd rule

The greatest-common-divisor rule confirms 8, choice (D).

gcd(99,999)=9, 9-1=8

Answer

The 8 interior points split segment AB into 9 equal pieces, each a step of (11,111). Adding 9 such steps to A(1,1) gives (1+99, 1+999)=(100,1000)=B, so the arithmetic closes exactly. The count also has to be less than 99, the number of available x-values, and 8 comfortably is. Choice (E) 9 is the natural trap: 9 is the number of equal pieces, or the count when B is mistakenly included.

💡Key takeaway

Put the slope in lowest terms; the line only touches grid points after whole copies of the reduced run, so count how many of those fit between the ends.

Slide A to the origin
Reduce the slope
Turn lattice point into divisibility
List the multiples of 11
Cross-check with the gcd rule

Slide A to the origin

Reduce the slope

Turn lattice point into divisibility

List the multiples of 11

Cross-check with the gcd rule

More like this