Question

Un conjunto de números se llama libre de sumas si cada vez 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$

Solución:

Podemos llegar a $10.$ Los impares $\{1, 3, 5, \ldots, 19\}$ son libres de sumas, ya que dos impares suman un par. También lo es $\{11, 12, \ldots, 20\},$ ya que cualesquiera dos de ellos suman más de $20.$ Cada uno tiene $10$ elementos. Ahora mostramos que no se puede superar $10.$ Sea $m$ el mayor elemento de un subconjunto libre de sumas. Empareja $1, 2, \ldots, m-1$ como $\{i, m-i\}.$ Un par no puede aportar ambos elementos, o su suma $m$ estaría en el conjunto. Hay $\lfloor (m-1)/2 \rfloor$ de esos pares, así que el subconjunto tiene como máximo $\lfloor (m-1)/2 \rfloor + 1$ $\le \lfloor 19/2 \rfloor + 1 = 10$ elementos. Por lo tanto, C es la respuesta correcta.

We can reach $10.$ The odds $\{1, 3, 5, \ldots, 19\}$ are sum-free, since two odds sum to an even. So is $\{11, 12, \ldots, 20\},$ since any two of those sum past $20.$ Each has $10$ elements. Now we show you can't beat $10.$ Let $m$ be the largest element of a sum-free subset. Pair up $1, 2, \ldots, m-1$ as $\{i, m-i\}.$ A pair can't contribute both elements, or their sum $m$ would be in the set. There are $\lfloor (m-1)/2 \rfloor$ such pairs, so the subset has at most $\lfloor (m-1)/2 \rfloor + 1$ $\le \lfloor 19/2 \rfloor + 1 = 10$ elements. Thus, C is the correct answer.

2025 AMC 10A Problema 21

Solución:

El Problema 21 en otros años