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

[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

[MateusQqMDMOD]

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.

[marcello10]

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

[jeabud]

MateusQqMD, como ficaria usando Kaplansky?

[MateusQqMDMOD]

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.

[MateusQqMDMOD]

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".

[jeabud]

MateusQqMD, obg