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$

Answer: B

Concepts:modular arithmetic subsets extremal argument

Difficulty rating: 1800

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,$ 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.

2012 AMC 12A Problem 17

Answer: B

Difficulty rating: 1800

Solution:

Problem 17 in Other Years