2025 AMC 12A Problema 15

Question

Un conjunto de números se llama libre de sumas si siempre que

x

y

y

son elementos (no necesariamente distintos) del conjunto,

x + y

no es un elemento del conjunto. Por ejemplo,

\{1, 4, 6\}

y el conjunto vacío son libres de sumas, pero

\{2, 4, 5\}

no lo es. ¿Cuál es el mayor número posible de elementos de un subconjunto libre de sumas de

\{1, 2, 3, \ldots, 20\}

?

A set of numbers is called sum-free if whenever

x

and

y

are (not necessarily distinct) elements of the set,

x + y

is not an element of the set. For example,

\{1, 4, 6\}

and the empty set are sum-free, but

\{2, 4, 5\}

is not. What is the greatest possible number of elements in a sum-free subset of

\{1, 2, 3, \ldots, 20\}?

8

9

10

11

12

Respuesta: C

Conceptos:subconjuntos argumento extremal

Nivel de dificultad: 1800

Pista pequeña:

El conjunto

\{11, 12, \ldots, 20\}

es libre de sumas

The set

\{11, 12, \ldots, 20\}

is sum-free

Pista grande:

Si

a_1 \lt \cdots \lt a_k

están en

S,

las diferencias

a_k - a_i

no están en

S,

lo que fuerza

2k - 1 \le 20

If

a_1 \lt \cdots \lt a_k

are in

S,

the differences

a_k - a_i

are not in

S,

forcing

2k - 1 \le 20

Solución:

El conjunto

\{11, 12, \ldots, 20\}

tiene

10

elementos y es libre de sumas, ya que dos elementos cualesquiera suman al menos

22 \gt 20.

Para la cota superior, sea

a_1 \lt a_2 \lt \cdots \lt a_k

un subconjunto libre de sumas. Cada diferencia

a_k - a_i

para

i \lt k

no puede estar en

S,

porque

(a_k - a_i) + a_i = a_k \in S

violaría la propiedad de ser libre de sumas.

Estas

k - 1

diferencias son distintas, están en

\{1, \ldots, 19\},

y son disjuntas de los

k

elementos de

S.

Así que

k + (k - 1) \le 20,

dando

k \le 10.

Por lo tanto, la respuesta correcta es C.

The set

\{11, 12, \ldots, 20\}

has

10

elements and is sum-free, since any two elements sum to at least

22 \gt 20.

For the upper bound, let

a_1 \lt a_2 \lt \cdots \lt a_k

be a sum-free subset. Each difference

a_k - a_i

for

i \lt k

cannot lie in

S,

because

(a_k - a_i) + a_i = a_k \in S

would violate sum-freeness.

These

k - 1

differences are distinct, lie in

\{1, \ldots, 19\},

and are disjoint from the

k

elements of

S.

So

k + (k - 1) \le 20,

giving

k \le 10.

Thus, the correct answer is C.