Escrito por Caique Paiva
Conhecimentos Prévios Necessários:
Seja o nosso conjunto resposta, ou seja, o conjunto de pares de elementos tal que tal que não está em e também não está em . Seja o conjunto complementar a esse, ou seja é o conjunto de pares de elementos tal que tal que está em ou está em . Veja que , pois eles são complementares, e a quantidade de pares tal que é . Então, para calcular podemos só calcular .
Seja o conjunto de pares com tal que está em , e o conjunto de pares com tal que está em . Pelo princípio da inclusão-exclusão, temos que
Mas veja que , portanto, podemos calcular separadamente. Então, vamos calcular esses 3!
- Passo 1: Calcular .
Vamos contar quantos pares existem tal que existem tal que está em . Vamos contar isso para cada elementos de . Veja que, para um , os pares tal que são os pares , portanto, temos pares para cada s_i. Então, é a soma de todas essas respostas.
- Passo 2: Calcular .
Vamos contar quantos pares existem tal que existem tal que está em . Vamos contar isso para cada elemento de . Veja que, para um elemento , os pares tal que são os pares , portanto, temos pares para um específico, então, é a soma de todas essas respostas.
- Passo 3: Calculas
Agora, vamos contar quantos pares existem tal que , está em e também está em . Escolha dois elementos de , sejam eles e . Veja que caso exista tal que e , resolvendo o sistema, temos que e , portanto, precisamos que sejam inteiros, e que . Para e serem inteiros, precisamos que e tenham a mesma paridade, e para , precisamos que . Logo, seja a quantidade de elementos pares de e a quantidade de elementos ímpares em , portanto, nossa resposta vai ser , já que .
Portanto, conseguimos calcular os 3 termos, e então conseguimos chegar na nossa resposta final.