Olimpíadas ⇒ (AIME-2002) Análise Combinatória Tópico resolvido

[gabrielifce]

Seja S={1,2,3,4,...,10}.Determine o número de pares não-ordenados A e B, onde são subconjuntos disjuntos não-nulos de S.

Resposta

---

28501

Estou aberto a Resolução ou idéia, tá valendo...
Bem a minha resolução
1-condição de x, y [tex3]\geq 1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\geq 1[/tex3]

2- introdução da variável de folga
A segunda foto é a contagem dos casos em que a [tex3]\geq 11[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\geq 11[/tex3]

, ao final somando tudo da 28, não multipliquei por 2, já que são pares não-ordenados[(a, b)=(b, a)], ou seja tá valendo para b também.
Por último a resposta...

[gabrielifce]

Alguém idéia? ?

[gabrielifce]

IAlguém tem idéia? ????

[gabrielifce]

Up

[ttbr96]

Há 10 elementos em S para criar os subconjuntos disjuntos A e B.

Para cada elemento de S há três possibilidades, ou seja, ela pode ser colocada em A ou em B ou nem em A nem em B.
Então, o número de par ordenado de subconjuntos disjuntos A e B é:

Código: Selecionar tudo

[tex3]3^{10}[/tex3]

.

Entretanto, nesta contagem há pares onde A ou B é vazio.
Se A for vazio há duas possibilidades para cada elemento de S, ou seja, ela pode estar em B ou não estar em B.
Então, o número de pares na qual A ou B é vazio é:

Código: Selecionar tudo

[tex3]2^{10} + 2^{10} - 1 = 2^{11} - 1[/tex3]

Mas o enunciado diz que são pares não ordenados (trocando A e B não resulta um conjunto diferente de subconjuntos, ou seja, {A, B} = {B, A}).
Assim, o número de conjuntos não ordenados A e B é:

Código: Selecionar tudo

[tex3]\frac{3^{10} - 2^{11} + 1}2 = 28501[/tex3]