2012 AMC 12A Problem 17

Let

S

be a subset of

\{1, 2, 3, \ldots, 30\}

with the property that no pair of distinct elements in

S

has a sum divisible by

5.

What is the largest possible size of

S?

Show solution

Solution

Group

\{1, \ldots, 30\}

by residue modulo

5;

each class has

6

numbers. A sum is divisible by

5

when the residues are

0{+}0,

1{+}4,

2{+}3.

S

can use at most one number

\equiv 0,

and only one of the classes

\{1\}, \{4\}

and only one of

\{2\}, \{3\}.

That allows at most

1 + 6 + 6 = 13

numbers. The set

\{1, 2, 6, 7, 11, 12,

16, 17, 21, 22,

26, 27, 30\}

achieves

13,

so the maximum is

13.

Thus, the correct answer is B.