Problema
Seja [tex]S[/tex] um conjunto com exatamente 6 elementos.
De quantos modos podemos formar dois subconjuntos de [tex]S[/tex], não necessariamente distintos, de modo que a união deles resulte em [tex]S[/tex]?
Solução
Indiquemos os subconjuntos por [tex]A[/tex] e [tex]B[/tex].
Assim, como distribuir os elementos de [tex]S[/tex] entre os conjuntos [tex]A[/tex] e [tex]B[/tex]?
Observe que, para cada um dos seis elementos do conjunto inicial [tex]S[/tex], temos três possibilidades:
- pertencer apenas ao subconjunto [tex]A[/tex];
- pertencer apenas ao subconjunto [tex]B[/tex];
- pertencer aos subconjuntos [tex]A[/tex] e [tex]B[/tex].
Haveria, então,[tex]3^6[/tex] modos de obtermos os subconjuntos [tex]A[/tex] e [tex]B[/tex].
Entretanto, distribuindo os elementos de [tex]S[/tex] nos conjuntos [tex]A[/tex] e [tex]B[/tex] dessa forma, não há distinção entre, por exemplo, as distribuições [tex]A= \{ a, b\}[/tex] e [tex]B= \{ c, d, e, f \}[/tex] e [tex]A= \{ c, d, e, f \}[/tex] e [tex]B= \{ a, b\}[/tex], já que ambas definem os mesmos subconjuntos [tex] \{ a, b \}[/tex] e [tex]\{ c, d, e, f \}[/tex], apenas com nomes diferentes.
Deste modo, com exceção da formação [tex]A = B = S[/tex], todas as demais foram contadas duas vezes.
Logo, temos [tex]\dfrac{3^6 – 1}{2} + 1 = 365[/tex] modos de formar os dois subconjuntos em questão.
Solução elaborada pelos Moderadores do Blog.
Nível C – Questão Difícil