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

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\le i<m/2,$ como $\{i,m-i\}$ Un par no puede aportar ambos elementos, o su suma $m.$ estaría en el conjunto. Hay $m$ de esos pares, así que el subconjunto tiene como máximo $m/2$ $m/2+m/2=m.$ elementos. Por lo tanto, C es la respuesta correcta. $m$ $\lfloor(m-1)/2\rfloor$ $\lfloor(m-1)/2\rfloor+1\le10.$

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<m/2,$ at most one member of $\{i,m-i\}$ can be chosen, because the two sum to $m.$ If $m$ is even, $m/2$ cannot be chosen either, since it can be used twice and $m/2+m/2=m.$ Thus besides $m$ there are at most $\lfloor(m-1)/2\rfloor$ chosen elements, for a total of at most $\lfloor(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

Solución:

El Problema 21 en otros años