- (Polônia) Determine o número de subconjuntos de
em que a equação
não possua solução.
Passo 1
Vou primeiro deixar claro o que o problema pede e o que nos é dado.
- O conjunto dado é
. - A equação considerada é
. - A pergunta é: “Quantos subconjuntos de
existem tais que a equação não tenha solução com e pertencendo ao subconjunto?”
Em outras palavras: contar os subconjuntos que não contêm nenhum par de elementos cuja soma seja.
Passo 2
Observação estrutural (formando pares): cada inteiro
em
tem um único companheiro
tal que
Portanto os elementos se agrupam em
pares disjuntos:
Esses pares são todos disjuntos (não se sobrepõem) e cobrem todo o conjunto
.
Passo 3
Entendimento da restrição: para que a equação
não tenha solução dentro de um subconjunto, esse subconjunto não pode conter, para nenhum desses pares, os dois elementos ao mesmo tempo. Ou seja, em cada par
devemos evitar escolher os dois elementos juntos.
Agora, para cada par temos exatamente três opções possíveis ao construir um subconjunto que respeite a restrição:
- não escolher nenhum dos dois elementos do par;
- escolher apenas o primeiro elemento do par;
- escolher apenas o segundo elemento do par.
Essas três opções cobrem todas as escolhas permitidas por par e excluem a escolha proibida (escolher os dois).
Passo 4
Independência entre pares e princípio multiplicativo: como os pares são disjuntos, a escolha feita em um par não afeta as escolhas nos outros pares. Pelo princípio multiplicativo (se um processo é composto por decisões independentes com
escolhas,
escolhas, etc., o total é o produto), o número total de subconjuntos válidos é o produto do número de opções em cada par.
Como há
pares e cada par oferece
opções, o total de subconjuntos que satisfazem a condição é
com
fatores.
Passo 5
Cheque rápido com exemplos pequenos para ganhar intuição:
- Para
: conjunto . Pares: . Subconjuntos permitidos: — são . - Para
: conjunto . Pares: . Cada par tem 3 opções, total . Dá para listar se quiser, confirma a fórmula.