Re: [obm-l] dúvida Epcar

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 02.09.03 01:02, tarciosd@ig.com.br at tarciosd@ig.com.br wrote:

> alguém poderia dar uma ajudinha. por favor nesta questão;
> 
> De quantos modos 3 casais podem sentar-se ao redor de uma mesa circular
> de tal forma que marido e mulher não fiquem juntos?
> 
> r= 32. como faço isso ??????
> 


Eu sou meio ruim de combinatoria. Entao, pra minimizar a chance de errar, eu
sempre procuro dividir esses problemas com restricoes em casos simples e
mutuamente exclusivos e calcular o numero de ocorrencias de cada um. No fim,
eh soh somar tudo...

Por exemplo, chame os pares de Aa, Bb e Cc.

Sejam:
ABC: no. de permutacoes em que os casais Aa, Bb, Cc ficam juntos.

AB: no. de permutacoes em que os casais Aa e Bb ficam juntos mas Cc fica
separado.
AC e BC: definidos analogamente.

A: no. de permutacoes em que Aa fica junto mas Bb e Cc ficam separados
B e C: definidos analogamente

X: no. de permutacoes em que todos ficam separados ==> esse eh o que
queremos calcular.

*****

Sabemos que o no. total de maneiras dos casais se sentarem sem restricoes eh
simplesmente o no. de permutacoes circulares de 6 elementos = 5! = 120.

Calculo de ABC:
Permutacoes circulares dos pares Aa, Bb e Cc: 2! = 2
No. de permutacoes do par Aa: 2  (A-a  ou  a-A)
No. de permutacoes do par Bb: 2
No. de permutacoes do par Cc: 2
ABC = 2^4 = 16

Calculo de AB:
Como Aa e Bb ficam juntos mas Cc fica separado, soh pode ser o caso que C e
c ocupam posicoes diametralmente opostas. Suponhamos que C esteja sentado:
No. de maneiras de sentar c: 1
No. de maneiras de sentar Aa e Bb, apos c ter sentado: 2
No. de permutacoes do par Aa: 2
No. de permutacoes do par Bb: 2
AB = 2^3 = 8
Analogamente, AC = BC = 8

Calculo de A:
Imaginemos o par Aa ja sentado (junto).
Vamos dividir em 2 casos:
(1) B senta junto de A ou de a;
(2) B nao senta junto de A nem de a.
Caso 1:
No. de maneiras de sentar B: 2
No. de maneiras de sentar b, apos B ter sentado: 1
No. de maneiras de sentar Cc, apos B e b terem sentado: 2
No. de permutacoes do par Aa: 2
Total caso 1 = 2^3 = 8.
Caso 2:
No. de maneiras de sentar B: 2
No. de maneiras de sentar b, apos B ter sentado: 1
No. de maneiras de sentar Cc, apos B e b terem sentado: 2
No. de permutacaoes do par Aa: 2
Total caso 2 = 2^3 = 8
Assim, A = 8 + 8 = 16.
Analogamente, B = C = 16

Agora, repare que todos os casos acima mais o caso pedido no enunciado sao
mutuamente exclusivos e esgotam todas as permutacoes circulares das 6
pessoas. Assim, podemos escrever:
5! = X + A + B + C + AB + AC + BC + ABC ==>
120 = X + 3*16 + 3*8 + 16 ==>
120 = X + 88 ==>
X = 32.


Um abraco,
Claudio.



=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================