Ola' Gabriel, a restricao que voce propos e' forte demais...:) Mas mesmo "capenga", o problema resultante ainda oferece alguma dificuldade - veja so' : Depois que voce posiciona a 1a esposa, quais as opcoes que existem para a 2a esposa? E para as outras?
[]'s Rogerio Ponce PS: a 1a esposa tinha 3 opcoes de encaixe. A 2a esposa talvez ainda tenha 3 opcoes de encaixe - vai depender de onde a 1a esposa foi posicionada. E assim por diante. ====================== Em 6 de fevereiro de 2012 00:30, Gabriel Merêncio < gmerencio.san...@gmail.com> escreveu: > 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) = 0 >> f(1) = 0 >> f(2) = 2 >> f(3) = 32 >> f(4) = 1488 >> f(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. >> >> >> >
