Date: Mon, 6 Feb 2012 00:30:26 -0200
Subject: [obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Permutação circular
From: gmerencio.san...@gmail.com
To: obm-l@mat.puc-rio.br
Desculpe se minha resolução não foi muito rigorosa, admito que me guiei mais
pela intuição... Pelo visto, com resultados pouco positivos.
Mas João, admitindo a restrição adicional de que dois homens não podem sentar
juntos (ou seja, todo homem senta ao lado de duas mulheres), acredito que seja
possível resolver facilmente por análise combinatória. Primeiro arranja-se os 5
homens de forma circular (separando cada um por uma posição vazia), o que pode
ser feito de 5!/5 = 4! = 24 maneiras. Uma esposa pode ocupar 3 das 5 posições
vazias, já que 2 ficam ao lado do marido, então há 3! = 6 maneiras de
distribuí-la. Portanto, 24 * 6 = 144 possibilidades no total. Generalizando, a
fórmula geral seria f(x) = (x - 1)! * (x - 2)!, sendo x o número de casais.
2012/2/5 João Maldonado <joao_maldona...@hotmail.com>
Não entendi seu raciocínio :(
Fiz um programa de computador que calcula todas as possibilidades da função
f(x), para x casais
obtive:f(0) = 0f(1) = 0f(2) = 2f(3) = 32f(4) = 1488f(5) = 112512
Se considerar que a formação horária é igual a anti-horária, divida ainda
por 2
Até o f(2) é fácil de se achar
Aqui vai todas as 192 (que é 32*6) possibilidades do f(3) em linha (ou
seja ,ignorando a igualdade por rotação e considerando que o primeiro termo
senta ao lado do último)
Sendo 0,1 o primeiro casal, 2,3 o segundo...
['021435', '021534', '024135', '024153', '024315', '025134', '025143',
'025314', '031425', '031524', '034125', '034152', '034215', '035124', '035142',
'035214', '041253', '041352', '042135', '042153', '042513', '043125', '043152',
'043512', '051243', '051342', '052134', '052143', '052413', '053124', '053142',
'053412', '120435', '120534', '124035', '124053', '124305', '125034', '125043',
'125304', '130425', '130524', '134025', '134052', '134205', '135024', '135042',
'135204', '140253', '140352', '142035', '142053', '142503', '143025', '143052',
'143502', '150243', '150342', '152034', '152043', '152403', '153024', '153042',
'153402', '203415', '203514', '204135', '204315', '204351', '205134', '205314',
'205341', '213405', '213504', '214035', '214305', '214350', '215034', '215304',
'215340', '240315', '240351', '240531', '241305', '241350', '241530', '243051',
'243150', '250314', '250341', '250431', '251304', '251340', '251430', '253041',
'253140', '302415', '302514', '304125', '304215', '304251', '305124', '305214',
'305241', '312405', '312504', '314025', '314205', '314250', '315024', '315204',
'315240', '340215', '340251', '340521', '341205', '341250', '341520', '342051',
'342150', '350214', '350241', '350421', '351204', '351240', '351420', '352041',
'352140', '402153', '402513', '402531', '403152', '403512', '403521', '405213',
'405312', '412053', '412503', '412530', '413052', '413502', '413520', '415203',
'415302', '420351', '420513', '420531', '421350', '421503', '421530', '425031',
'425130', '430251', '430512', '430521', '431250', '431502', '431520', '435021',
'435120', '502143', '502413', '502431', '503142', '503412', '503421', '504213',
'504312', '512043', '512403', '512430', '513042', '513402', '513420', '514203',
'514302', '520341', '520413', '520431', '521340', '521403', '521430', '524031',
'524130', '530241', '530412', '530421', '531240', '531402', '531420', '534021',
'534120']
Para o f(3) tenho um método para achar o 32 (muito pouco prático), serve
também para qualquer x, mas depois do f(3) fica quase impossível de se fazer
as coisas sem um computador.
Tentei achar uma recursão mas não consegui (aliás pela fatoração dos
resultados, tal recursão teria que ter muitas somas já que 112512 por exemplo
tem fator 293, ou seja, provavelmente não seria viável
Para o caso específico de homem sentar ao lado de mulher achei uma recursão
e uma fórmula fácil (se você entende de teoria do caos).
[]'s
João
Date: Sun, 5 Feb 2012 16:39:02 -0200
Subject: [obm-l] Re: [obm-l] Permutação circular
From: gmerencio.san...@gmail.com
To: obm-l@mat.puc-rio.br
Meu raciocínio é considerar cada casal como uma reta, sendo definida por dois
pontos: um é o assento do marido e o outro o da esposa. Temos um total de C(10,
2) retas para representar o primeiro casal. Para descontar as configurações
iguais por rotação, dividimos esse número por 5. Finalmente, sabemos que
exatamente 2 dessas retas são inválidas, pois nelas o marido fica ao lado de
sua esposa (já descontamos as outras obtidas por rotação) .
Continuando a lógica para os 8 assentos restantes, vemos que agora dividimos
por 4, já que um casal já está à mesa. Resultados semelhantes podem ser
inferidos para 6 e depois 4 assentos restantes, só restando 1 possibilidade
para o último par. Portanto:
[C(10,2)/5 - 2] * [C(8,2)/4 - 2] * [C(6,2)/3 - 2] * [C(4,2)/2 - 2] * 1 = = 7 *
5 * 3 * 1 * 1 == 105
2012/1/27 Carlos Gomes <cgomes...@gmail.com>
Olá amigos...alguém poderia me ajudr com a
questão:
De quantas formas distintas 5 casais podem ser
dispostos em torno de uma mesa circular, supondo que cada marido não fique ao
lado da sua respectiva esposa?
(Duas conficurações são consideradas iguais se uma
puder ser obtida da outroa por um movimento de rotação!)
Obrigado, Cgomes.
