2021 AMC 12B Spring Problem 25

Question

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?

31

47

62

72

85

Answer: E

Concepts:lattice point floor and ceiling functions

Difficulty rating: 2600

Small hint:

For a given

m,

column

x

contributes

\min(30,\lfloor mx\rfloor)

points at or below the line

Big hint:

As

m

increases, the count jumps at slopes

\tfrac{y}{x};

find the two consecutive such slopes bracketing a count of

300

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.

At

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.

If

\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.