Segunda, 05 Novembro 2018 19:54

ANTONIO CLAUDIO LAGE BUFFARA RESPONDE: QUESTÕES PUC-RIO - DÚVIDA EPCAR

Escrito por

Hoje publicarei um problema que foi compartilhado na lista PUC-RIO.

DÚVIDA

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?

SOLUÇÃO

Eu sou meio ruim de combinatória. Então, para minimizar a chance de errar, eu sempre procuro dividir esses problemas com restrições em casos simples e mutuamente exclusivos e calcular o número de ocorrências de cada um. No fim, é só somar tudo.

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

Sejam:

ABC: nº de permutações em que os casais Aa, Bb, Cc ficam juntos.

AB: nº de permutações em que os casais Aa e Bb ficam juntos mas Cc fica separado.

AC e BC: definidos analogamente.

A: nº de permutações em que Aa fica junto mas Bb e Cc ficam separados

B e C: definidos analogamente

X: nº de permutações em que todos ficam separados ==> esse é o que queremos calcular.

Sabemos que o nº total de maneiras dos casais se sentarem sem restrições é simplesmente o nº de permutações circulares de 6 elementos = 5! = 120.

Cálculo de ABC:

Permutações circulares dos pares Aa, Bb e Cc: 2! = 2

Nº de permutações do par Aa: 2 (A-a ou a-A)

Nº de permutações do par Bb: 2

Nº de permutações do par Cc: 2

ABC = 2^4 = 16

Cálculo de AB:

Como Aa e Bb ficam juntos mas Cc fica separado, só pode ser o caso que C e c ocupam posições diametralmente opostas. Suponhamos que C esteja sentado:

Nº de maneiras de sentar c: 1

Nº de maneiras de sentar Aa e Bb, após c ter sentado: 2

Nº de permutações do par Aa: 2

Nº de permutações do par Bb: 2

AB = 2^3 = 8

Analogamente, AC = BC = 8

Cálculo de A:

Imaginemos o par Aa já sentado (junto)

Vamos dividir em 2 casos:

(1) B senta junto de A ou de a;

(2) B não senta junto de A nem de a.

Caso 1:

Nº de maneiras de sentar B: 2

Nº de maneiras de sentar b, após B ter sentado: 1

Nº de maneiras de sentar Cc, após B e b terem sentado: 2

Nº de permutações do par Aa: 2

Total caso 1 = 2^3 = 8.

Caso 2:

Nº de maneiras de sentar B: 2

Nº de maneiras de sentar b, após B ter sentado: 1

Nº de maneiras de sentar Cc, após B e b terem sentado: 2

Nº de permutações 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 são mutuamente exclusivos e esgotam todas as permutações 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.

Confira a discussão completa em: http://www.mat.puc-rio.br/~obmlistas/obm-l.200309/msg00021.html

Ler 761 vezes Última modificação em Segunda, 05 Novembro 2018 20:02

Deixe um comentário

Certifique-se de preencher os campos indicados com (*). Não é permitido código HTML.