2021 AMC 10B 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

\frac ab,

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: 2390

Small hint:

Near the relevant slopes, the number of points is

\sum_{x=1}^{30}\lfloor mx\rfloor

Big hint:

Find the slope where the

300

th lattice-point ratio occurs and the next larger possible ratio

Solution:

For a fixed slope

m,

the number of points in

S

on or below

y=mx

is

\sum_{x=1}^{30}\lfloor mx\rfloor,

for the slopes near the answer.

At

m=\frac23,

grouping

x=3k+1,3k+2,3k+3

for

k=0,1,\ldots,9

gives

\lfloor \frac{2x}{3}\rfloor=2k,\ 2k+1, \ 2k+2,

whose sum over each block is

6k+3.

Thus the total is

\sum_{k=0}^9(6k+3)=270+30=300.

If

m<\frac23,

the ten points with ratios

\frac{y}{x}=\frac{2}{3}

are no longer counted, so the count is less than

300.

Therefore the lower end is

\frac23.

The next possible ratio

\frac{y}{x}

greater than

\frac23,

with

1\le x,y\le30,

is minimized by checking

x

modulo

3.

The best candidates are

\frac{19}{28},\qquad \frac{20}{29},\qquad \frac{21}{30}=\frac{7}{10},

and the smallest is

\frac{19}{28}.

Hence the interval length is

\frac{19}{28}-\frac23=\frac1{84}.

Thus

a+b=1+84=85.

Thus, the answer is E .