(A) Problema para ajudar na escola: Subconjuntos e somas

Problema
(A partir do 9º ano do E. F. – Nível de dificuldade: Difícil)

$\{245896 \, , \, 985639541 \, , \, 609326959806695631 \, , \, 56823682 \, , \, 147546085389595866 \, , \, 487935968565873\}$

têm a propriedade de que a soma de seus elementos é um número par.

Solução

• três pares;
• dois pares e um ímpar;
• um par e dois ímpares;
• três ímpares.

Analisando a paridade das somas dos três números nos quatro casos apresentados, temos que:

• $par+par+par=par$;
• $par+par+ímpar=ímpar$;
• $par+ímpar+ímpar=par$;
• $ímpar+ímpar+ímpar=ímpar$.

Pela exigência do problema, a soma dos três números deve ser um número par, então nos interessa saber quantos subconjuntos com "três números pares" e quantos com "um número par e dois ímpares" podemos formar, a partir do conjunto dado. Vejamos:

$\textcolor{#800000}{(i)}$ Como temos apenas três números pares, será possível construir apenas um subconjunto com três números pares.

$\textcolor{#800000}{(ii)}$ Para a escolha de um número par e dois ímpares, podemos escolher o número par de três modos diferentes. Para cada uma dessas escolhas, temos que escolher dois dentre os ímpares possíveis:

• o primeiro ímpar pode ser escolhido de três formas diferentes, já que temos três ímpares no conjunto dado;
• escolhido o primeiro ímpar, podemos escolher o segundo de duas maneiras diferentes.

A princípio, teríamos então $3 \times 3 \times 2 = 18$ maneiras de escolher os três números.
$\qquad \qquad \begin{array}{c c c c c} 3& \, &3& \, &2\\ \overline{\text{único par}}& \, &\overline{\text{primeiro ímpar}}& \, & \overline{\text{segundo ímpar}}\\ \end{array}$

No entanto, observe que os conjuntos $\{par \, , \, ímpar_1 \, , \, ímpar_2 \, \}$ e $\{par \, , \, ímpar_2 \, , \, ímpar_1 \, \}$ são iguais. Assim, fixado um número $par$, escolher o $ímpar_1$ e, em seguida, o $ímpar_2$, vai produzir o mesmo subconjunto resultante de escolhermos o $ímpar_2$ e em seguida o $ímpar_1$. Dessa forma, devemos dividir as $18$ maneiras de escolher os três números por dois, para não contarmos duas vezes os conjuntos que tenham os mesmos números ímpares em sua composição. Com isso teremos $\dfrac{18}{2}=9$ maneiras de escolher um par e dois ímpares.
Observação: Escolhido o número par, observamos que "escolher dois entre os três ímpares é equivalente a escolher um dos três para ficar de fora". Assim, temos três maneiras de escolher o que não irá ficar no conjunto e, com isso, teríamos as mesmas $3 \times 3 =9$ maneiras de escolher os três números, sendo um par e dois ímpares.
$\qquad \qquad \begin{array}{c c c} 3& \, &3\\ \overline{\text{único par}}& \, &\overline{\text{dois ímpares}}\\ \end{array}$

Portanto, por $\textcolor{#800000}{(i)}$ e $\textcolor{#800000}{(ii)}$, temos $\fcolorbox{black}{#eee0e5}{$1+9=10$}$ subconjuntos com a propriedade de que a soma de seus elementos é um número par.

Solução elaborada pelos Moderadores do Blog.