Questão 7. Considere o conjunto S=\{1,2,3, \ldots, n\}. Para cada um de seus subconjuntos não vazios, definimos a soma alternante desse subconjunto como segue: Arranje os números do subconjunto em ordem decrescente e então, iniciando pelo maior, alternadamente adicione e subtraia os números do subconjunto sucessivamente. Por exemplo, a soma alternante para o subconjunto \{1,2,4,6,9\} é +9-6+4-2+1=6 e a soma alternante do subconjunto \{5\} é apenas 5 . Ache a soma de todas as somas alternantes de todos os subconjuntos de S quando \mathrm{n}=10.

Passo 1

O enunciado dá o conjunto S=\{1,2,\dots,10\}. Para cada subconjunto não vazio de S definimos a “soma alternante” arranjando os elementos em ordem decrescente e fazendo + no maior, - no segundo maior, + no terceiro, e assim por diante.
A pergunta é: qual é a soma de todas as somas alternantes de todos os subconjuntos não vazios de S quando n=10?

Passo 2

Vamos reescrever a soma que queremos de modo a poder trocar a ordem das somas (isso facilita muito). Seja T a soma desejada, isto é a soma, sobre todos os subconjuntos não vazios A\subseteq S, da soma alternante de A. Se k\in A, denote por s(k,A) o sinal atribuído a k na soma alternante de A; então a soma alternante de A é \sum_{k\in A}s(k,A)\,k. Portanto
T=\sum_{\substack{A\subseteq S\A\neq\varnothing}}\sum_{k\in A}s(k,A)\,k.
Pela linearidade da soma podemos trocar as somas e escrever
T=\sum_{k=1}^{10} k\cdot\Bigg(\sum_{\substack{A\subseteq S\k\in A}} s(k,A)\Bigg).

Passo 3

Agora precisamos entender s(k,A) para um k fixo e todos os subconjuntos A que contêm k. O sinal de k depende só de quantos elementos maiores que k aparecem em A. Se em A houver exatamente r elementos maiores que k, então k fica na posição r+1 quando se ordena decrescentemente, e o sinal será (+1) se r for par e (-1) se r for ímpar. Assim podemos escrever
s(k,A)=(-1)^r,
onde r é o número de elementos de A que são maiores que k.

Passo 4

Para um k fixo, conte as escolhas de A que contêm k. Há dois tipos de escolhas independentes:
  • escolha de quais dos 10-k elementos maiores que k entram em A; se escolhermos exatamente r desses, há \binom{10-k}{r} formas;
  • escolha de quais dos k-1 elementos menores que k entram em A; qualquer subconjunto desses pode entrar, total 2^{\,k-1} formas.
Portanto, o número de subconjuntos A contendo k com exatamente r elementos maiores que k é \binom{10-k}{r}\cdot 2^{\,k-1}, e todos esses subconjuntos contribuem com sinal (-1)^r para a soma interna.

Passo 5

Assim a soma interna para um k fixo é
\sum_{\substack{A\subseteq S\k\in A}} s(k,A) =2^{\,k-1}\sum_{r=0}^{10-k} (-1)^r\binom{10-k}{r}.
Aqui aparece a soma binomial alternada \sum_{r=0}^{m}(-1)^r\binom{m}{r}. Pelo binômio de Newton, para qualquer inteiro m\ge0 vale
\sum_{r=0}^{m}(-1)^r\binom{m}{r}=(1-1)^m.
Portanto essa soma vale 0 se m\ge1 e vale 1 se m=0.

Passo 6

No nosso caso m=10-k. Logo para todo k com 10-k\ge1 (isto é, para k\le9) a soma \sum_{r=0}^{10-k}(-1)^r\binom{10-k}{r} é 0. Apenas quando 10-k=0, isto é k=10, a soma é 1. Concluímos que todos os termos com k=1,2,\dots,9 se cancelam e só resta o termo k=10.

Passo 7

Para k=10 temos 2^{\,k-1}=2^{9} subconjuntos possíveis dos menores que podem acompanhar o 10, e o sinal sempre é +1. Assim
T = 10\cdot 2^{9}.
Nota: 2^{9}=512, mas deixo a multiplicação final para a resposta.

Passo 8

Interpretação intuitiva (útil para prova): para cada k<10 há exatamente tantas aparições com sinal + quanto com sinal - quando se varrem todos os subconjuntos, por isso se cancelam. O maior elemento 10 nunca é “ofuscado” por um maior, então seu coeficiente líquido é o número total de subconjuntos que o contêm, ou seja 2^{9}.

Resposta

5120

Exercícios relacionados