Question

Para cada subconjunto no vacío de $\{1,2,3,\ldots,n\}$ , se define una suma alternada única de la siguiente manera: ordena los números del subconjunto en orden decreciente y luego, empezando por el mayor, suma y resta alternativamente los números sucesivos. (Por ejemplo, la suma alternada de $\{1,2,4,6,9\}$ es $9-6+4-2+1=6$ , y para $\{5\}$ es simplemente $5.$ ) Halla la suma de todas estas sumas alternadas para $n=7.$

For $\{1,2,3,\ldots,n\}$ and each of its nonempty subsets a unique alternating sum is defined as follows: Arrange the numbers in the subset in decreasing order and then, beginning with the largest, alternately add and subtract successive numbers. (For example, the alternating sum for $\{1,2,4,6,9\}$ is $9-6+4-2+1=6$ and for $\{5\}$ it is simply $5.$ ) Find the sum of all such alternating sums for $n=7.$

Respuesta

Respuesta: 448

Conceptos:subconjuntos doble conteo teorema del binomio

Nivel de dificultad: 2650

Pista pequeña:

Suma por separado la contribución de cada número sobre todos los subconjuntos

Add the contribution of each number separately over all subsets

Pista grande:

El signo de $k$ depende solo de si el subconjunto contiene un número par o impar de elementos mayores que $k$

The sign of $k$ depends only on whether the subset contains an even or odd number of elements greater than $k$

Solución:

Fija $k.$ Una vez incluido $k,$ los $k-1$ elementos menores se pueden elegir arbitrariamente, lo que aporta un factor de $2^{k-1}.$ Si se eligen exactamente $j$ de los $7-k$ elementos mayores, el signo de $k$ es $(-1)^j.$ Por tanto, el coeficiente de $k$ en el total es $\begin{aligned} &2^{k-1}\sum_{j=0}^{7-k} (-1)^j\binom{7-k}{j}\\ &\qquad=2^{k-1}(1-1)^{7-k}. \end{aligned}$ Esto es $0$ para $k<7$ y $2^6$ para $k=7.$ Por consiguiente, el total es $7\cdot2^6=448.$

Fix $k.$ Once $k$ is included, the $k-1$ smaller elements may be chosen arbitrarily, contributing a factor of $2^{k-1}.$ If exactly $j$ of the $7-k$ larger elements are chosen, the sign of $k$ is $(-1)^j.$ Therefore the coefficient of $k$ in the total is $\begin{aligned} &2^{k-1}\sum_{j=0}^{7-k} (-1)^j\binom{7-k}{j}\\ &\qquad=2^{k-1}(1-1)^{7-k}. \end{aligned}$ This is $0$ for $k<7$ and $2^6$ for $k=7.$ Hence the total is $7\cdot2^6=448.$

1983 AIME Problema 13

Respuesta: 448

Nivel de dificultad: 2650

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años