2012 AMC 12A Problem 17

Question

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?

10

13

15

16

18

Sort the numbers by their remainder modulo

5

; there are

6

numbers in each class

Residues

1

and

4

cannot both appear, nor can

2

and

3,

and at most one multiple of

5

is allowed

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,

or

2{+}3.

So

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.

Problem 17 in other years