Consegui...
Observe que o primeiro termo de [tex3]S[/tex3]
mais o último é igual a [tex3]2n+1[/tex3]
; analogamente o segundo mais o penúltimo também é igual a [tex3]2n+1[/tex3]
... É fácil ver que qualquer subconjunto de [tex3]S[/tex3]
que contenha termos simétricos (tipo primeiro e último, segundo e penúltimo...) contém uma solução para a equação dada.
Logo, nosso problema se reduz a achar a quantidade de subconjuntos de [tex3]S[/tex3]
que não contenha termos simétricos. Chamemos este conjuntos de
anti-simétricos (só para poder me referir melhor a eles)
- Subconjuntos anti-simétricos de [tex3]S[/tex3] que possuem nenhum elemento
É fácil ver que só há um conjunto deste tipo (i.e. o conjunto vazio)
- Subconjuntos anti-simétricos de [tex3]S[/tex3] com apenas um elemento.
Bem, qualquer conjunto unitário é anti-simétrico, logo há [tex3]2n[/tex3]
conjuntos neste caso
- Subconjuntos anti-simétricos de [tex3]S[/tex3] com dois elementos
Bem, inicialmente podemos escolher qualquer um dos [tex3]2n[/tex3]
elementos de [tex3]S[/tex3]
para formar um conjunto desse caso, depois nos restarão [tex3]2n-2[/tex3]
elementos a escolher (pois não podemos escolher nem o que foi escolhido inicialmente nem o simétrico em relação a este mesmo).
A princípio, o principio multiplicativo nos leva a concluir que há [tex3]2n\cdot (2n-2)=2^2\cdot n(n-1)[/tex3]
conjuntos neste caso; entretanto, devemos nos lembrar que um subconjunto [tex3]\{a,b \}[/tex3]
e outro conjunto [tex3]\{b,a\}[/tex3]
são, em verdade, um só. Portanto, há [tex3]\dfrac{2^2\cdot n(n-1)}{2}=2^2\cdot {n\choose 2}[/tex3]
na verdade (mais tarde verá porque eu escrevi desta forma).
- Subconjuntos anti-simétricos de [tex3]S[/tex3] com [tex3]3[/tex3] elementos.
Continuando o raciocínio anterior, podemos escolher [tex3]2n[/tex3]
para ser o primeiro elemento do conjunto, depois podemos escolher [tex3]2n-2[/tex3]
para o segundo e por fim [tex3]2n-4[/tex3]
para o terceiro.
Inicialmente, podemos pensar que há [tex3]2n(2n-2)(2n-4)=2^3n(n-1)(n-2)[/tex3]
; entretanto estamos considerando cada conjunto [tex3]3![/tex3]
vezes. Assim, em verdade, há [tex3]2^3\cdot \dfrac{n(n-1)(n-2)}{3!}=2^3\cdot {n\choose 3}[/tex3]
conjuntos (eu acho que já dá para perceber o padrão).
Generalizando, para a quantidade de subconjuntos
anti-simétricos de [tex3]S[/tex3]
formados [tex3]k[/tex3]
elementos ...
Podemos inicialmente escolher [tex3]2n[/tex3]
números para a primeiro elemento, depois [tex3]2n-2[/tex3]
para o segundo... por fim podemos escolher [tex3]2n-2(k-1)[/tex3]
para o último ( Para verificar que este é o valor para o último é só observar os resultados para os outros números, ou se quer ser mais formal, usar indução)
Inicialmente, o princípio multiplicativo nos leva a crer que há [tex3]2n\cdot (2n-2)\cdot (2n-4)\cdot \dots \cdot (2n-2(k-1))=2^k\cdot n(n-1)(n-2)...(n-(k-1))[/tex3]
que pode ser reescrito como [tex3]2^k\cdot \dfrac{n!}{(n-k)!}[/tex3]
. Entretanto, desta forma cada subconjunto está sendo levado em consideração [tex3]k![/tex3]
vezes. Assim, o valor real é [tex3]2^k\cdot \dfrac{n!}{k!\cdot (n-k)!}=2^k\cdot {n\choose k}[/tex3]
.
Portanto, a resposta do nosso problema é [tex3]\displaystyle\sum_{k=0}^{n}2^k\cdot {n\choose k}[/tex3]
(o limite superior só vai até [tex3]n[/tex3]
pois para [tex3]k>n[/tex3]
aquele produto seria nulo). Mas... isto não te lembra nada? Esta é exatamente a fórmula do binômio de Newton para [tex3]1+2[/tex3]
, eu quero dizer pelo binômio de Newton [tex3](1+2)^n=\displaystyle\sum_{k=0}^{n}2^k\cdot 1^{n-k}\cdot {n\choose k}[/tex3]
(observe que [tex3]1^{n-k}=1[/tex3]
)
Assim a resposta do nosso problema é [tex3](1+2)^n=3^n[/tex3]
