IME / ITA(AIME) Conjuntos Tópico resolvido

Aqui deverão ser postadas questões desses vestibulares e de outras instituições militares (EN, CN, EsPCEx etc.).

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
Teu
iniciante
Mensagens: 2
Registrado em: Seg 16 Jul, 2018 10:49
Última visita: 29-07-18
Jul 2018 16 17:52

(AIME) Conjuntos

Mensagem não lida por 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




Avatar do usuário
fismatpina
2 - Nerd
Mensagens: 218
Registrado em: Seg 26 Jun, 2017 10:29
Última visita: 07-05-19
Jul 2018 18 15:33

Re: (AIME) Conjuntos

Mensagem não lida por fismatpina »

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

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

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

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

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

Logo a única solução possível é [tex3]|C| = 101[/tex3] e [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]

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

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

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

:D



Jack of all trades :wink:

Avatar do usuário
Killin
3 - Destaque
Mensagens: 1085
Registrado em: Ter 28 Jun, 2016 15:31
Última visita: 20-12-23
Jul 2018 18 15:47

Re: (AIME) Conjuntos

Mensagem não lida por Killin »

fismatpina escreveu:
Qua 18 Jul, 2018 15:33
Logo a única solução possível é
Como a gente pode ter certeza disso?


Life begins at the end of your comfort zone.

Avatar do usuário
fismatpina
2 - Nerd
Mensagens: 218
Registrado em: Seg 26 Jun, 2017 10:29
Última visita: 07-05-19
Jul 2018 18 15:50

Re: (AIME) Conjuntos

Mensagem não lida por fismatpina »

Killin escreveu:
Qua 18 Jul, 2018 15:47
fismatpina escreveu:
Qua 18 Jul, 2018 15:33
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 :wink:

Última edição: fismatpina (Qua 18 Jul, 2018 15:51). Total de 1 vez.


Jack of all trades :wink:

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem (AIME) Fatoração
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    823 Exibições
    Última msg por NigrumCibum
  • Nova mensagem (AIME) Fatoração
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    805 Exibições
    Última msg por Ittalo25
  • Nova mensagem (AIME) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    780 Exibições
    Última msg por Ittalo25
  • Nova mensagem (AIME) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    758 Exibições
    Última msg por Ittalo25
  • Nova mensagem (AIME) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    715 Exibições
    Última msg por Ittalo25

Voltar para “IME / ITA”