2021 AMC 12B Problem 25

Problem 25 of 25HarderAlgebra Geometry

Let

S

be the set of lattice points in the coordinate plane, both of whose coordinates are integers between

1

and

30,

inclusive. Exactly

300

points in

S

lie on or below a line with equation

y=mx.

The possible values of

m

lie in an interval of length

\dfrac{a}{b},

where

a

and

b

are relatively prime positive integers. What is

a+b?

Show solution

Solution

For slope

m,

column

x

(with

1\le x\le 30

) contributes

\min(30,\lfloor mx\rfloor)

points on or below

y=mx,

and we need the total to equal

300.

m=\tfrac23,

the cap at

30

is inactive and

\sum_{x=1}^{30}\lfloor \frac{2x}{3}\rfloor=300.

The count remains fixed until the next larger slope

\frac{y}{x}

with

x\le30.

\frac{y}{x}>\frac{2}{3},

then

3y-2x

is a positive integer. The closest possibility has

3y-2x=1;

maximizing

x\le30

in this congruence gives

(y,x)=(19,28).

Any numerator at least

2

gives a larger gap. Hence the interval is

[\tfrac23,\tfrac{19}{28}),

whose length is

\tfrac{19}{28}-\tfrac23=\tfrac1{84}.

Since

\gcd(1,84)=1,

a+b=1+84=85.

Thus, the correct answer is E.