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

Respuesta: 901

Conceptos:subconjuntos argumento extremal conteo de enteros en un rango

Nivel de dificultad: 1890

Pista pequeña:

Halla la menor y la mayor suma posibles, luego muestra que todo valor entre ellas se alcanza

Find the smallest and largest possible sums, then show every value between them occurs

Pista grande:

Si la suma no es máxima, algún elemento

k

de

\mathcal{A}

cumple

k + 1 \notin \mathcal{A};

reemplazar

k

por

k + 1

aumenta la suma exactamente en

1

If the sum is not maximal, some element

k

of

\mathcal{A}

has

k + 1 \notin \mathcal{A};

replacing

k

by

k + 1

raises the sum by exactly

1

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

Respuesta: 901

Nivel de dificultad: 1890

Pista pequeña:

Pista grande:

Solución:

El Problema 2 en otros años