Question

Sea $\mathcal{A}$ un subconjunto de $90$ elementos de $\{1, 2, 3, \ldots, 100\},$ y sea $S$ la suma de los elementos de $\mathcal{A}.$ Halla el número de valores posibles de $S.$

Let set $\mathcal{A}$ be a $90$ -element subset of $\{1, 2, 3, \ldots, 100\},$ and let $S$ be the sum of the elements of $\mathcal{A}.$ Find the number of possible values of $S.$

Respuesta

Solución:

La menor suma posible es $1 + 2 + \cdots + 90 = 4095,$ y la mayor es $11 + 12 + \cdots + 100 = 4995.$

Todo entero intermedio también se alcanza. Supón que $\mathcal{A}$ tiene suma $S \le 4994,$ y sea $k$ el menor elemento de $\mathcal{A}$ con $k + 1 \notin \mathcal{A}.$ Si $k$ fuera $100,$ entonces $\mathcal{A}$ sería un bloque de enteros consecutivos que termina en $100,$ es decir $\{11, \ldots, 100\},$ cuya suma supera $4994.$ Por tanto $k \ne 100,$ y reemplazar $k$ por $k + 1$ produce un subconjunto de $90$ elementos con suma $S + 1.$

Por lo tanto $S$ toma todos los valores desde $4095$ hasta $4995,$ lo que da $4995 - 4095 + 1 = 901$ valores posibles.

The smallest possible sum is $1 + 2 + \cdots + 90 = 4095,$ and the largest is $11 + 12 + \cdots + 100 = 4995.$

Every integer in between also occurs. Suppose $\mathcal{A}$ has sum $S \le 4994,$ and let $k$ be the smallest element of $\mathcal{A}$ with $k + 1 \notin \mathcal{A}.$ If $k$ were $100,$ then $\mathcal{A}$ would be a block of consecutive integers ending at $100,$ namely $\{11, \ldots, 100\},$ whose sum exceeds $4994.$ So $k \ne 100,$ and replacing $k$ by $k + 1$ produces a $90$ -element subset with sum $S + 1.$

Hence $S$ takes every value from $4095$ to $4995,$ for $4995 - 4095 + 1 = 901$ possible values.

2006 AIME I Problema 2

Solución:

El Problema 2 en otros años