2012 AMC 12A Problema 17

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.