Concursos PúblicosAnálise Combinatória - primeiro lema de Kaplansky Tópico resolvido

Este é o fórum para postagem de problemas cobrados em Concursos Públicos.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
marcello10
iniciante
Mensagens: 8
Registrado em: Qui 27 Dez, 2018 17:07
Última visita: 17-04-19
Jan 2019 10 22:58

Análise Combinatória - primeiro lema de Kaplansky

Mensagem não lida por marcello10 »

De acordo com o primeiro lema de Kaplansky, a quantidade de subconjuntos de {1, 2, 3,..., n} com p elementos, em que não há números consecutivos, é dada pela fórmula seguinte: [tex3]\frac{(n-p+1)!}{p!(n-2p+1)!} [/tex3] .

Uma breve explicação sobre tal lema:
Uma das aplicações desse lema é a contagem do número de maneiras de se sentar quatro meninas e seis meninos em uma fila de dez cadeiras, de modo que duas meninas não fiquem em posições adjacentes. A estratégia para se realizar essa contagem compreende quatro passos. Em primeiro lugar, deve-se contar o número de maneiras de se escolher quatro cadeiras sem que haja cadeiras consecutivas; esse procedimento deve ser feito utilizando-se o lema de Kaplansky. Em seguida, deve-se contar o número de maneiras de organizar as meninas nessas cadeiras. O próximo passo consiste em contar o número de maneiras de se distribuir os meninos nas cadeiras restantes. Por fim, deve-se usar o princípio multiplicativo.

(Cespe – UnB – TRE-ES – 2011) Diante dos dados acima, é correto afirmar que o número de maneiras de se sentar quatro meninas e seis meninos em uma fila de dez cadeiras, de modo que não fiquem duas meninas em posições adjacentes, é superior a 600 mil.
Resposta

Certo




Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2693
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 21-02-24
Localização: Fortaleza/CE
Jan 2019 11 10:51

Re: Análise Combinatória - primeiro lema de Kaplansky

Mensagem não lida por MateusQqMD »

O número de modos de organizarmos os 6 meninos em fila é [tex3]P_6 = 6![/tex3] . Por exemplo, uma dessas configurações é


[tex3]\begin{array}{ccccccccc}
\underline{} & \text{M}_1 & \underline{} & \text{M}_2 & \underline{} & \text{M}_3 & \underline{} & \text{M}_4 & \underline{} & \text{M}_5 & \underline{}& \text{M}_6 & \underline{}\\
1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 \\

\end{array}[/tex3]

Note, agora, que todos os espaços assinalados correspondem a espaços não consecutivos. Portanto, devemos arrumar as 4 meninas nesses espaços. Como em cada lugar só pode entrar uma menina, basta escolhermos 4 espaços entre os 7 disponíveis, [tex3]C_7^4 = \frac{7!}{4!3!}[/tex3] . Em seguida, devemos colocar as 4 meninas nos 4 lugares selecionados, o que pode ser feito de [tex3]4![/tex3] modos

A resposta é [tex3]6! \cdot C_7^4 \cdot 4! = 604800[/tex3]

Se você quiser eu posso resolver usando Kaplansky, sai até mais rápido, mas eu considero essa resolução mais intuitiva.



"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."

Avatar do usuário
Autor do Tópico
marcello10
iniciante
Mensagens: 8
Registrado em: Qui 27 Dez, 2018 17:07
Última visita: 17-04-19
Jan 2019 11 10:58

Re: Análise Combinatória - primeiro lema de Kaplansky

Mensagem não lida por marcello10 »

Cara, muito obrigado, quando eu tentei fazer, não pensei em distribuir os meninos e meninas, obrigado mesmo.



Avatar do usuário
jeabud
Ultimate
Mensagens: 820
Registrado em: Dom 01 Set, 2019 19:06
Última visita: 24-02-24
Nov 2020 09 10:34

Re: Análise Combinatória - primeiro lema de Kaplansky

Mensagem não lida por jeabud »

MateusQqMD, como ficaria usando Kaplansky?



Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2693
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 21-02-24
Localização: Fortaleza/CE
Nov 2020 09 11:27

Re: Análise Combinatória - primeiro lema de Kaplansky

Mensagem não lida por MateusQqMD »

Olá, jeabud.

Ficaria [tex3]C_{7}^{4}[/tex3] (escolha dos lugares não consecutivos) vezes [tex3]4![/tex3] (modos de arrumar as meninas nesses lugares) vezes [tex3]6![/tex3] (modos de arrumar os meninos nos lugares restantes.

A ideia é escolher, em primeiro lugar, os lugares não consecutivos pelo Primeiro Lema de Kaplanksy. Há 10 cadeiras ao total e podemos escolher quatro lugares não consecutivos de [tex3]\binom{10-4+1}{4} = C_7^4[/tex3] modos... e o restante da resolução é bem tranquila. Há [tex3]4![/tex3] modos de arrumar as meninas nesses locais. Há [tex3]6![/tex3] modos de arrumar os meninos nos locais não escolhidos inicialmente.


"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."

Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2693
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 21-02-24
Localização: Fortaleza/CE
Nov 2020 09 11:29

Re: Análise Combinatória - primeiro lema de Kaplansky

Mensagem não lida por MateusQqMD »

A primeira resolução é o modo como chegamos ao resultado proposto pelo Primeiro Lema. Então, acaba que as resoluções são "as mesmas".


"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."

Avatar do usuário
jeabud
Ultimate
Mensagens: 820
Registrado em: Dom 01 Set, 2019 19:06
Última visita: 24-02-24
Nov 2020 10 07:45

Re: Análise Combinatória - primeiro lema de Kaplansky

Mensagem não lida por jeabud »

MateusQqMD, obg




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Concursos Públicos”