Question

Sea $S = \{2^0, 2^1, 2^2, \ldots, 2^{10}\}.$ Considera todas las posibles diferencias positivas de pares de elementos de $S.$ Sea $N$ la suma de todas estas diferencias. Halla el resto cuando $N$ se divide entre $1000.$

Let $S = \{2^0, 2^1, 2^2, \ldots, 2^{10}\}.$ Consider all possible positive differences of pairs of elements of $S.$ Let $N$ be the sum of all of these differences. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

En la suma de todas las diferencias positivas, el elemento $2^k$ se suma una vez por cada elemento menor ( $k$ veces) y se resta una vez por cada elemento mayor ( $10 - k$ veces). Por tanto $\begin{aligned} N &= \sum_{k=0}^{10} (2k - 10)\,2^k \\ &= 2\sum_{k=0}^{10} k\,2^k - 10\sum_{k=0}^{10} 2^k. \end{aligned}$

Las sumas estándar son $\sum_{k=0}^{10} k\,2^k = 9 \cdot 2^{11} + 2 = 18434$ y $\sum_{k=0}^{10} 2^k = 2^{11} - 1 = 2047,$ de modo que $\begin{aligned} N &= 2 \cdot 18434 - 10 \cdot 2047 \\ &= 36868 - 20470 = 16398. \end{aligned}$

El resto al dividir entre $1000$ es $398.$

In the sum of all positive differences, the element $2^k$ is added once for each smaller element ( $k$ times) and subtracted once for each larger element ( $10 - k$ times). Hence $\begin{aligned} N &= \sum_{k=0}^{10} (2k - 10)\,2^k \\ &= 2\sum_{k=0}^{10} k\,2^k - 10\sum_{k=0}^{10} 2^k. \end{aligned}$

The standard sums are $\sum_{k=0}^{10} k\,2^k = 9 \cdot 2^{11} + 2 = 18434$ and $\sum_{k=0}^{10} 2^k = 2^{11} - 1 = 2047,$ so $\begin{aligned} N &= 2 \cdot 18434 - 10 \cdot 2047 \\ &= 36868 - 20470 = 16398. \end{aligned}$

The remainder upon division by $1000$ is $398.$

2009 AIME I Problema 8

Solución:

El Problema 8 en otros años