Operação com conjuntos (combinatória)

Pode ser contado diretamente, ou provado por indução, por exemplo.  Se m = 1, A tem um elemento, e não é possível realizar nenhuma operação. Logo, a fórmula funciona nesse caso. Supondo verdadeira para m elementos, se A tem m+1 elementos, a primeira operação transforma esse conjunto em dois conjuntos de cardinalidade m. Em cada um deles é possível realizar \(2^{m-1} -1\) operações. Logo, o total possível de operações é \( 2(2^{m-1} -1 1) + 2 = 2^m - 1\). Portanto, segue por indução o resultado.

Se A = {a,b} então os conjuntos finais são {|a+b|}, {|a-b|}. Se A  = { a,b,c} os conjuntos finais serão {|a+b+c|}, {|-a+b+c|}, {|a-b+c|}, {|a+b-c|}. Teste alguns casos, encontre um padrão e prove!

Seja \(A = \{ a_1, a_2, \cdots, a_m\}\). Primeiro observamos que qualquer conjunto unitário obtido ao final das operações tem um elemento da forma \(  \pm a_1 \pm a_2 \pm \cdots \pm a_m \) para alguma escolha de sinais. Agora observamos que temos \(2^{m}\) desses elementos e apenas \(2^{m-1} \) conjuntos. Isso significa que temos mais números da forma \(  \pm a_1 \pm a_2 \pm \cdots \pm a_m \) do que conjuntos. Mais precisamente, temos o dobro de números.  Para simplificar, vamos considerar A  = {a,b,c}. Dessa forma, as possíveis escolhas de sinais são:
+a+b+c
-a+b+c
+a-b-c
+a+b-c
-a-b+c
-a+b-c
+a-b-c
-a-b-c

Ou seja, temos 8 possibilidades. Notamos que
|+a+b+c| = |-a-b-c|
|-a+b+c| = |+a-b-c|
|+a-b+c| = |-a+b-c|
|+a+b-c| = |-a-b+c|
Esses são justamente os 4 elementos finais. Repare que se para alguma escolha de sinais, digamos a-b+c, temos soma positiva, isto é, a-b+c ≥ 0, então na "escolha simétrica" (trocando todos os sinais) teremos soma negativa: -a+b-c ≤ 0. E a como a operação sempre privilegia a soma positiva, no final o resultado obtido é apenas uma das duas possibilidades.

Pra ver que de fato todas as "escolhas de sinais a menos de simetria" de fato ocorrem, basta mostrar como produzir cada uma delas. Isso é equivalente a dizer qual sequencia de conjuntos/elementos escolhemos até obter um conjunto unitário. Segue o algoritmo (vou dar um exemplo apenas, pois é mais fácil do que explicar o caso geral). Digamos que A = {a,b,c,d,e}  e que queremos chegar no conjunto {|+a-b+c-d+e|}. Para isso, escolhemos dois elementos quaisquer de A e aplicamos a operação. Vamos supor que escolhemos os elementos a,b. Com isso obtemos os conjuntos
{a+b,c,d,e} e { a-b,c,d,e}
(o segundo conjunto poderia ser b-a, a depender de quem é maior, mas vamos supor que é a-b)

Notamos que em +a-b+c-d+e, os sinais de a e b são distintos. Por isso, vamos continuar a operação com o conjunto {a-b,c,d,e}. Escolhemos novamente 2 elementos, digamos que foram c,e. Com isso produzimos dois conjuntos, mas como os sinais de c,e são iguais em +a-b+c-d+e, o unico que interessa é:
{a-b,c+e,d}
Realizamos denovo a operação, digamos que escolhemos a-b, c+e. Cada termo já possui 2 parcelas, mas o importante é que na expressão +a-b+c-d+e, "a-b" tem sinal igual a "c+e". Assim, o conjunto escolhido será:
{a-b+c+e,d}
Por fim, observamos que na expressão a-b+d+e deve ter sinal oposto a d. Assim, o conjunto final será:
{(a-b+c+e)-d}  = {a-b+c-d+e}
(poderia ser {d-(a-b+c+e)} = {-a+b-c+d-e} a depender de quem é maior, mas o ponto é que conseguimos obter |+a-b+c-d+e|)

De maneira geral, para produzir uma "escolha de sinais" basta proceder dessa forma. Isso verifica que os conjuntos finais não dependem da ordem das operações feitas.

Observamos que:
2-1 = 4-3 , daí: -1+2+3-4 = 0
6-5 = 8-7, daí:  -5+6+7-8 = 0
Logo, em geral caso seja m = 4k, temos:
(-1+2+3-4) + (-5+6+7- + (-9+10 +11-12) + ... + ( -(m-3)+(m-2)+(m-1)-m ) = 0
Logo, existe uma escolha de sinais do conjunto {1,2,3,...,m} que tem zero como resultado, caso seja m = 4k

Para m = 4k+3, similarmente temos:
(-1 -2 + 3) + (-4+5+6-7) + (-8+9+10-11) + ...+ ( -(m-3)+(m-2)+(m-1)-m ) = 0
Novamente existe uma escolha de sinais produzindo zero.
Portanto nesses casos, {0} é um conjunto final

Basta verificar que caso seja m = 4k+1 ou m = 4k+1, qualquer soma da forma:
±­1±­2±­3±­...±­m
é impar!! Em particular, não pode ser zero!

Observamos que caso {0} seja um conjunto final de A = {1,2,...,m}, então existe uma escolha de sinais
±­1±­2±­3±­...±­m
cuja soma é zero. Como 1+2+...+m = m(m+1)/2, isso é equivalente a dividir o conjunto A em uma união disjunta B∪C, onde a soma dos elementos de cada conjunto é m(m+1)/4. Seja B o conjunto que contém o elemento 1 e seja B' = {2}∪ B'', o conjunto obtido multiplicando-se cada elemento de B por 2. Notamos que B'' está contido em {4,...,2m} e que a soma dos elementos de B'' é m(m+1)/2 - 2.

Isto é, o problema de encontrar um subconjunto de {4,...,2m} cuja soma dos elementos é igual a m(m+1)/2 - 2 é equivalente a encontrar uma escolha de sinais de ±­1±­2±­3±­...±­m cuja soma é 0.
Obs.: essa pergunta está aqui porque esse outro problema combinatório apareceu em outra solução dada para o problema de cálculo original!!.