1985 AIME Problem 10

Question

How many of the first

1000

positive integers can be expressed in the form

\lfloor2x\rfloor+\lfloor4x\rfloor+\lfloor6x\rfloor+\lfloor8x\rfloor,

where

x

is a real number, and

\lfloor z\rfloor

denotes the greatest integer less than or equal to

z?

Answer

Substitute

y=2x

and separate

y

into its integer and fractional parts

Determine the values of

\lfloor r\rfloor+\lfloor2r\rfloor+\lfloor3r\rfloor+\lfloor4r\rfloor

for

0\leq r\lt1

Let

y=2x=m+r,

where

m

is an integer and

0\leq r\lt1.

The expression is

10m+\lfloor r\rfloor+\lfloor2r\rfloor+\lfloor3r\rfloor+\lfloor4r\rfloor.

Checking the breakpoints

r=\frac{1}{4},

\frac{1}{3},

\frac{1}{2},

\frac{2}{3},

\frac{3}{4}

shows that the fractional-part contribution takes exactly the values

0,

1,

2,

4,

5,

and

6.

Thus precisely six residue classes modulo

10

are attainable. Among the first

1000

positive integers, this gives

100\cdot6=600.

Problem 10 in other years