Escrito por Caique Paiva
Conhecimentos Prévios Necessários:
Seja $$C$$ o nosso conjunto resposta, ou seja, o conjunto de pares de elementos $$(x, y)$$ tal que $$0 \le x \le y \le c$$ tal que $$x+y$$ não está em $$s$$ e $$y-x$$ também não está em $$s$$. Seja $$C’$$ o conjunto complementar a esse, ou seja $$C’$$ é o conjunto de pares de elementos $$(x, y)$$ tal que $$0 \le x \le y \le c$$ tal que $$x+y$$ está em $$s$$ ou $$y-x$$ está em $$s$$. Veja que $$|C| + |C’| = (c+1)^2/2$$, pois eles são complementares, e a quantidade de pares $$(x, y)$$ tal que $$0 \le x \le y \le c$$ é $$(c+1)^2/2$$. Então, para calcular $$|C|$$ podemos só calcular $$|C’|$$.
Seja $$A$$ o conjunto de pares $$(x, y)$$ com $$0 \le x \le y \le c$$ tal que $$x+y$$ está em $$s$$, e $$B$$ o conjunto de pares $$(x, y)$$ com $$0 \le x \le y \le c$$ tal que $$y-x$$ está em $$s$$. Pelo princípio da inclusão-exclusão, temos que
$$|A \cup B| = |A| + |B| – |A \cap B|$$
Mas veja que $$A \cup B = C’$$, portanto, podemos calcular $$|A|, |B|, |A \cap B|$$ separadamente. Então, vamos calcular esses 3!
- Passo 1: Calcular $$|A|$$.
Vamos contar quantos pares $$(x, y)$$ existem tal que $$0 \le x \le y \le c$$ existem tal que $$x+y$$ está em $$s$$. Vamos contar isso para cada elementos de $$s$$. Veja que, para um $$s_i$$, os pares $$(x, y)$$ tal que $$x+y = s_i$$ são os pares $$(0, s_i), (1, s_i – 1), (2, s_i – 2), \cdots ( \lfloor \frac{s_i}{2} \rfloor , \lceil \frac{s_i}{2} \rceil )$$, portanto, temos $$\lfloor \frac{s_i}{2} \rfloor + 1$$ pares para cada s_i. Então, $$|A|$$ é a soma de todas essas respostas.
- Passo 2: Calcular $$|B|$$.
Vamos contar quantos pares $$(x, y)$$ existem tal que $$0 \le x \le y \le c$$ existem tal que $$y-x$$ está em $$s$$. Vamos contar isso para cada elemento de $$s$$. Veja que, para um elemento $$s_i$$, os pares $$(x, y)$$ tal que $$y-x = s_i$$ são os pares $$(c-s_i, c), (c-s_i – 1, c-1), \cdots, (0, s_i)$$, portanto, temos $$c-s_i + 1$$ pares para um $$i$$ específico, então, $$|B|$$ é a soma de todas essas respostas.
- Passo 3: Calculas $$|A \cup B|$$
Agora, vamos contar quantos pares $$(x, y)$$ existem tal que $$0 \le x \le y \le c$$, $$x+y$$ está em $$s$$ e $$y-x$$ também está em $$s$$. Escolha dois elementos de $$s$$, sejam eles $$s_i$$ e $$s_j$$. Veja que caso exista $$(x, y)$$ tal que $$x+y = s_i$$ e $$y-x = s_j$$, resolvendo o sistema, temos que $$x = \frac{s_i – s_j}{2}$$ e $$y = \frac{s_i + s_j}{2}$$, portanto, precisamos que $$x, y$$ sejam inteiros, e que $$x \ge 0$$. Para $$x$$ e $$y$$ serem inteiros, precisamos que $$s_i$$ e $$s_j$$ tenham a mesma paridade, e para $$x \ge 0$$, precisamos que $$s_i \ge s_j$$. Logo, seja $$p$$ a quantidade de elementos pares de $$s$$ e $$q$$ a quantidade de elementos ímpares em $$s$$, portanto, nossa resposta vai ser $$\frac{p(p+1)}{2} + \frac{q(q+1)}{2}$$, já que $$s_i \ge s_j$$.
Portanto, conseguimos calcular os 3 termos, e então conseguimos chegar na nossa resposta final.