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$

Respuesta: B

Conceptos:aritmética modular subconjuntos argumento extremal

Nivel de dificultad: 1800

Pista pequeña:

Ordena los números por su residuo módulo $5$ ; hay $6$ números en cada clase

Sort the numbers by their remainder modulo $5$ ; there are $6$ numbers in each class

Pista grande:

Los residuos $1$ y $4$ no pueden aparecer ambos, ni tampoco $2$ y $3,$ y se permite a lo sumo un múltiplo de $5$

Residues $1$ and $4$ cannot both appear, nor can $2$ and $3,$ and at most one multiple of $5$ is allowed

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

Respuesta: B

Nivel de dificultad: 1800

Pista pequeña:

Pista grande:

Solución:

El Problema 17 en otros años