IME / ITA ⇒ (AIME) Conjuntos Tópico resolvido

[Teu]

(AIME) Dados conjuntos A, B e C, sejam |A|,|B|,|C| suas quantidades de elementos, respectivamente, e sejam s(A), s(B), s(C) suas quantidades de subconjuntos, respectivamente. Sabendo que |A| = |B| = 100 e s(A) + s(B) + s(C) = s(A∪B∪C), determine:

a. |C|
b. |A ∪ B ∪ C|
c. o valor mínimo de |A ∩ B ∩ C|

Resposta

---

a-101
b-102
c-97

[fismatpina]

Sabemos que s(A) = [tex3]2^{|A|}[/tex3]

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

[tex3]2^{|A|}[/tex3]

, assim:

s(A) + s(B) + s(C) = s(A∪B∪C)

[tex3]2^{|A|} + 2^{|B|} + 2^{|C|}[/tex3]

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

[tex3]2^{|A|} + 2^{|B|} + 2^{|C|}[/tex3]

= [tex3]2^{|A∪B∪C|}[/tex3]

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

[tex3]2^{|A∪B∪C|}[/tex3]

[tex3]2^{100} + 2^{100} + 2^{|C|} = 2^{|A∪B∪C|}[/tex3]

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

[tex3]2^{100} + 2^{100} + 2^{|C|} = 2^{|A∪B∪C|}[/tex3]

[tex3]2^{101} + 2^{|C|} = 2^{|A∪B∪C|}[/tex3]

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

[tex3]2^{101} + 2^{|C|} = 2^{|A∪B∪C|}[/tex3]

Logo a única solução possível é [tex3]|C| = 101[/tex3]

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

[tex3]|C| = 101[/tex3]

e [tex3]|A∪B∪C| = 102[/tex3]

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

[tex3]|A∪B∪C| = 102[/tex3]

Pela desigualdade de Bon Ferroni, temos que o números de elementos da interseção é maior ou igual ao número de elementos de cada conjunto menos (n-1) vezes o número de elementos do universo (onde n é o número de conjuntos aplicados nessa interseção). No caso são três conjuntos (A, B e C), assim temos:

[tex3]|A∩B∩C| \geq |A|+|B|+|C| - (3-1).|A∪B∪C|[/tex3]

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

[tex3]|A∩B∩C| \geq |A|+|B|+|C| - (3-1).|A∪B∪C|[/tex3]

[tex3]|A∩B∩C| \geq 100+100+101-2(102) = 301 - 204[/tex3]

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

[tex3]|A∩B∩C| \geq 100+100+101-2(102) = 301 - 204[/tex3]

[tex3]|A∩B∩C| \geq 97[/tex3]

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

[tex3]|A∩B∩C| \geq 97[/tex3]

Finalmente, o valor mínimo de [tex3]|A∩B∩C|[/tex3]

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

[tex3]|A∩B∩C|[/tex3]

é então [tex3]97[/tex3]

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

[tex3]97[/tex3]

[Killin]

Logo a única solução possível é

Como a gente pode ter certeza disso?

[fismatpina]

Logo a única solução possível é

Como a gente pode ter certeza disso?

São inteiros positivos e são expoentes de potências de 2. Então só essas soluções satisfazem tais condições do problema