2013 AMC 12A Problem 20

Problem 20 of 25HarderNumber Theory Combinatorics

Let

S

be the set

\{1, 2, 3, \ldots, 19\}.

For

a,

b \in S,

define

a \succ b

to mean that either

0 \lt a - b \le 9

or

b - a \gt 9.

How many ordered triples

(x, y, z)

of elements of

S

have the property that

x \succ y,

y \succ z,

and

z \succ x?

Show solution

Solution

Reading the elements modulo

19,

the relation

a \succ b

holds exactly when

0 \lt (a - b) \bmod 19 \le 9.

There are

19

choices for

x.

Once

x

is fixed, take

y = x + i

for some

1 \le i \le 9.

Then

z

must satisfy

x + 10 \le z \le x + 9 + i,

giving

i

choices. The total is

19(1 + 2 + \cdots + 9) = 19\cdot 45

= 855.

Thus, the correct answer is B.

Tagged: modular arithmetic · basic counting

More practice