Question

Sea $S$ un subconjunto de $\{1, 2, 3, \ldots, 30\}$ con la propiedad de que ningún par de elementos distintos de $S$ tiene una suma divisible entre $5.$ ¿Cuál es el mayor tamaño posible de $S$ ?

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$

Solución:

Agrupa $\{1, \ldots, 30\}$ por residuo módulo $5;$ cada clase tiene $6$ números. Una suma es divisible entre $5$ cuando los residuos son $0{+}0,$ $1{+}4,$ o $2{+}3.$

Así que $S$ puede usar a lo sumo un número $\equiv 0,$ y solo una de las clases $\{1\}, \{4\}$ y solo una de $\{2\}, \{3\}.$ Eso permite a lo sumo $1 + 6 + 6 = 13$ números.

El conjunto $\{1, 2, 6, 7, 11, 12,$ $16, 17, 21, 22,$ $26, 27, 30\}$ alcanza $13,$ así que el máximo es $13.$

Por lo tanto, la respuesta correcta es B.

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 Problema 17

Solución:

El Problema 17 en otros años