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$

Respuesta: C

Conceptos:subconjuntos argumento extremal emparejamiento y agrupación

Nivel de dificultad: 2120

Pista pequeña:

Tanto $\{1, 3, 5, \ldots, 19\}$ como $\{11, 12, \ldots, 20\}$ son libres de sumas, cada uno con $10$ elementos.

Both $\{1, 3, 5, \ldots, 19\}$ and $\{11, 12, \ldots, 20\}$ are sum-free, each with $10$ elements

Pista grande:

Si $m$ es el mayor elemento, empareja $1$ hasta $m-1$ como $\{i, m-i\};$ cada par aporta como máximo un elemento.

If $m$ is the largest element, pair $1$ to $m-1$ as $\{i, m-i\};$ each pair contributes at most one element

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 sea $m$ el mayor elemento de un subconjunto libre de sumas cualquiera. Para $1\le i<\frac{m}{2},$ a lo sumo se puede elegir un elemento de $\{i,m-i\}$ , porque los dos suman $m.$ Si $m$ es par, tampoco se puede elegir $\frac{m}{2}$ , ya que puede usarse dos veces y $\frac{m}{2}+\frac{m}{2}=m.$ Así, además de $m$ hay a lo sumo $\lfloor\frac{m-1}{2}\rfloor$ elementos elegidos, para un total de a lo sumo $\lfloor\frac{m-1}{2}\rfloor+1\le10.$ Por lo tanto, el mayor tamaño posible es $10.$ Así, 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 let $m$ be the largest element of any sum-free subset. For $1\le i<\frac{m}{2},$ at most one member of $\{i,m-i\}$ can be chosen, because the two sum to $m.$ If $m$ is even, $\frac{m}{2}$ cannot be chosen either, since it can be used twice and $\frac{m}{2}+\frac{m}{2}=m.$ Thus besides $m$ there are at most $\lfloor\frac{m-1}{2}\rfloor$ chosen elements, for a total of at most $\lfloor\frac{m-1}{2}\rfloor+1\le10.$ Therefore the greatest possible size is $10.$ Thus, C is the correct answer.

2025 AMC 10A Problema 21

Respuesta: C

Nivel de dificultad: 2120

Pista pequeña:

Pista grande:

Solución:

El Problema 21 en otros años