Olimpíadas ⇒ (Áustria/Polônia-99) Análise combinatória Tópico resolvido

[Caduzin3445]

(Áustria/Polônia-99) Sejam [tex3]n[/tex3] um inteiro positivo e [tex3]M = \{1,\,2,\,...,\,n\}[/tex3]. Determine o número de maneiras de formar seis subconjuntos [tex3]A_1[/tex3], [tex3]A_2[/tex3], [tex3]A_3[/tex3], [tex3]A_4[/tex3], [tex3]A_5[/tex3] e [tex3]A_6[/tex3] (não necessariamente disjuntos) de [tex3]M[/tex3], de modo que cada elemento de [tex3]M[/tex3] pertença a 0, 3 ou 6 dos conjuntos [tex3]A_1[/tex3], [tex3]A_2[/tex3], [tex3]A_3[/tex3], [tex3]A_4[/tex3], [tex3]A_5[/tex3] e [tex3]A_6[/tex3].

Resposta

---

Gab: [tex3]22^n[/tex3]

[Xablauu]

A ideia do problema é pensar que cada elemento de M pode estar em nenhum conjunto, ou pode estar nos conjuntos A_i, A_j, A_k, ou pode estar em todos. Essa escolha para cada elemento de M é independente.
# = Número de maneiras.

#(Nenhum conjunto) = 1
#(conjuntos A_i, A_j, A_k) = 6 escolhe 3
#(Todos os conjuntos) = 1

#(Total) = 1 + (6 escolhe 3) +1 = 22

Como a escolha é independente, a resposta final é [tex3]22^n[/tex3]