Problemas da Semana 42 - Problema Avançado - Solução

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Princípio da Inclusão-Exclusão

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.

Clique aqui para ver o código