Questão 7. Considere o conjunto
. 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
é
e a soma alternante do subconjunto
é apenas 5 . Ache a soma de todas as somas alternantes de todos os subconjuntos de S quando
.
Passo 1
O enunciado dá o conjunto
. Para cada subconjunto não vazio de
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 quando
?
A pergunta é: qual é a soma de todas as somas alternantes de todos os subconjuntos não vazios de
Passo 2
Vamos reescrever a soma que queremos de modo a poder trocar a ordem das somas (isso facilita muito). Seja
a soma desejada, isto é a soma, sobre todos os subconjuntos não vazios
, da soma alternante de
. Se
, denote por
o sinal atribuído a
na soma alternante de
; então a soma alternante de
é
. Portanto
Pela linearidade da soma podemos trocar as somas e escrever
Passo 3
Agora precisamos entender
para um
fixo e todos os subconjuntos
que contêm
. O sinal de
depende só de quantos elementos maiores que
aparecem em
. Se em
houver exatamente
elementos maiores que
, então
fica na posição
quando se ordena decrescentemente, e o sinal será
se
for par e
se
for ímpar. Assim podemos escrever
onde
é o número de elementos de
que são maiores que
.
Passo 4
Para um
fixo, conte as escolhas de
que contêm
. Há dois tipos de escolhas independentes:
- escolha de quais dos
elementos maiores que entram em ; se escolhermos exatamente desses, há formas; - escolha de quais dos
elementos menores que entram em ; qualquer subconjunto desses pode entrar, total formas.
Portanto, o número de subconjuntos
contendo
com exatamente
elementos maiores que
é
, e todos esses subconjuntos contribuem com sinal
para a soma interna.
Passo 5
Assim a soma interna para um
fixo é
Aqui aparece a soma binomial alternada
. Pelo binômio de Newton, para qualquer inteiro
vale
Portanto essa soma vale
se
e vale
se
.
Passo 6
No nosso caso
. Logo para todo
com
(isto é, para
) a soma
é
. Apenas quando
, isto é
, a soma é
. Concluímos que todos os termos com
se cancelam e só resta o termo
.
Passo 7
Para
temos
subconjuntos possíveis dos menores que podem acompanhar o
, e o sinal sempre é
. Assim
Nota:
, mas deixo a multiplicação final para a resposta.
Passo 8
Interpretação intuitiva (útil para prova): para cada
há exatamente tantas aparições com sinal
quanto com sinal
quando se varrem todos os subconjuntos, por isso se cancelam. O maior elemento
nunca é “ofuscado” por um maior, então seu coeficiente líquido é o número total de subconjuntos que o contêm, ou seja
.