user f.k.a. Cabeção escreveu:Essa foi a estratégia que eu pensei também, só não sei se é a única (é claro, desconsiderando a mesma estratégia começando-se pela 17ª caverna).
Dante, the Wicked escreveu:Posso estar enganado, mas este problema proposto pelo Cabeção é NP (não-polinomial). Ou seja, não há um algorítimo para uma simples resolução. Apenas um de tentativa e erro.
Problema difícil mesmo é resolver a conjectura P=NP?
Avatar escreveu:
Enquanto ninguém responde se conhece, ou deseja conhecer, o problema das 12 pérolas, vou apresentar um mais fácil e mais conhecido:
O problema das oito pérolas
Diz-se que um Rei possuía oito pérolas exatamente iguais em tamanho, formato e cor. Uma, porém, era ligeiramente mais leve que as outras. Intentando conhecer a capacidade de raciocínio de seus súditos, ele lançou o seguinte desafio: determinar, utilizando-se uma balança comum de dois pratos e com apenas duas pesagens, qual era a pérola mais leve, com precisão matemática.
Quem se habilita? Não vale para quem já conhece a resposta, olha a honestidade...
O outro problema, o das 12 pérolas, por ser mais complicado até para enunciá-lo, só o farei se houver interesse por parte dos senhores.
King In Crimson escreveu:0 vale?
Partiti escreveu:Primeiro pesamos 4 bolas contra 4 bolas, deixando outras 4 de lado. Temos daí 2 resultados possíveis:
1º - Há equilíbrio => Então pesamos 3 das 4 bolas não pesadas ainda contra 3 das já pesadas;
->Se há equilíbrio, então a bola não pesada que é a falsa, bastando compará-la com uma já pesada para ver se é mais leve ou mais pesada
->Se há desequilíbrio, então saberemos se a bola falsa é mais leve ou pesada, pois o prato das bolas não pesadas na primeira pesagem vai subir ou descer nesta pesagem, para o caso da bola falsa ser mais leve ou pesada, respectivamente . Daí basta pesar 2 das 3 bolas entre si, se houver equilíbrio, a bola falsa é a restante. Se não houver equilíbrio, a bola que realizar a mesma coisa que na 2ª pesagem é a falsa.
2º - Há desequilíbrio => Então pegamos 3 bolas de um prato (prato 1), 2 bolas do outro (prato 2) e comparamos com as 4 bolas não pesadas e a bola que sobrou do prato 1. Daí teremos 2 casos:
->Se há equilíbrio, então as 2 bolas não pesadas na segunda pesagem devem ser pesadas entre si, a que estiver no prato que realizar o mesmo movimento da primeira pesagem é a falsa, e será mais leve/pesada pelo movimento que realizou.
->Se há desequilíbrio => Então observamos se o prato com as bolas não pesadas realiza o mesmo movimento que a bola deste prato que veio do prato 1 realizou na primeira pesagem:
Se sim, pesamos as 2 bolas que vieram do prato 2 entre si, Se houver equilíbrio, esta única bola é a falsa e será a mais leve/pesada pelo movimento que realizou na primeira pesagem. Se houver desequilíbrio, a bola que realizar o mesmo movimento da primeira pesagem é a falsa e novamente será a mais leve ou pesada dependendo do movimento que realizou.
Se não, pesamos 2 das 3 bolas que vieram do prato 1, Se houver equilíbrio, a bola que sobrou do prato 1 é a falsa, e será a mais leve/pesada dependendo do movimento que realizou na primeira pesagem. Se houver desequilíbrio, então a bola que realizar o mesmo movimento da primeira pesagem que será a falsa, e novamente saberemos se é mais leve/pesada pelo movimento realizado.
Ufa, espero que entendam, é muito difícil explicar...
user f.k.a. Cabeção escreveu:
O Partiti está "correcto".
Vou passar um da mesma revista que quebrei a cabeça para fazer (não vale olhar as respostas). Esse eu levei pelo menos meia hora para arranjar a solução. E é bem legal.
Osama bin Laden está escondido numa montanha que possui 17 cavernas em linha, e ele está numa delas. Essas cavernas estão numeradas da 1ª até a 17ª, e bin Laden se comunicou com George W. Bush passando as regras que ditariam a busca nessas caverna. Os militares americanos só poderiam vasculhar duas cavernas por dia, e deveriam achá-lo em no máximo duas semanas. Em contrapartida, o terrorista se comprometeu em limitar seus movimentos a apenas se mudar para a caverna à sua esquerda ou à sua direita, sem opção de ficar parado. Se Bush não cumprir o prometido ele explodirá tudo.
Crie (descubra) uma estratégia para locálizá-lo em no máximo duas semanas (14 rodadas).
Adianto que o problema é complexo, ou pelo menos foi para mim.
Avatar escreveu:
De fato, Partiti, é muito difícil explicar a resolução do problema e, talvez por isso, eu não tenha entendido corretamente. No entanto, eu encontrei algumas inconsistências na sua resposta. A primeira esta na parte que eu selecionei em vermelho. Vejamos:
Se você pesar entre si duas pérolas que foram deixadas de lado na segunda pesagem, teremos apenas um resultado esperado onde um prato subiria e outro desceria. Não há como determinar onde está a pérola diferente. Observe com atenção e você perceberá o erro. Outro detalhe que evidencia que a proposta não está correta é que você afirma, na segunda tentativa, que teríamos duas situações possíveis, quando, na verdade, teríamos três. Com efeito, se você trocou pérolas entre as balanças, retirou algumas, excluíndo-as da nova pesagem, e manteve outras ainda, considerando que qualquer uma delas poderia ser a falsa, a balança poderia manter o desequilibrio inicial, poderia equilibrar ou inverter o desequilíbrio entre os pratos.
Também não sei se consegui explicar direito.
Código: Selecionar todos
1 2 3 4 5 6 7 8 9 10 11 12Partiti escreveu:Avatar escreveu:
De fato, Partiti, é muito difícil explicar a resolução do problema e, talvez por isso, eu não tenha entendido corretamente. No entanto, eu encontrei algumas inconsistências na sua resposta. A primeira esta na parte que eu selecionei em vermelho. Vejamos:
Se você pesar entre si duas pérolas que foram deixadas de lado na segunda pesagem, teremos apenas um resultado esperado onde um prato subiria e outro desceria. Não há como determinar onde está a pérola diferente. Observe com atenção e você perceberá o erro. Outro detalhe que evidencia que a proposta não está correta é que você afirma, na segunda tentativa, que teríamos duas situações possíveis, quando, na verdade, teríamos três. Com efeito, se você trocou pérolas entre as balanças, retirou algumas, excluíndo-as da nova pesagem, e manteve outras ainda, considerando que qualquer uma delas poderia ser a falsa, a balança poderia manter o desequilibrio inicial, poderia equilibrar ou inverter o desequilíbrio entre os pratos.
Também não sei se consegui explicar direito.
Vou tentar numerar as bolas:Código: Selecionar todos
1 2 3 4 5 6 7 8 9 10 11 12
Na parte em vermelho em especial, nós pesamos as bolas 1, 2, 3 e 4 contra as bolas 5, 6, 7 e 8 e costatamos um desequilíbrio. Esse desequilíbrio garante que as bolas 9, 10, 11 e 12 são "normais". Vamo supor também que esse desequilíbrio garante que as bolas 5, 6, 7 e 8 são mais pesadas que as bolas
1, 2, 3 e 4
Na segunda vez pesamos as bolas 2, 3, 4, 5 e 6 contra as bolas 1, 9, 10, 11 e 12 e constatamos que há equilíbrio, garantindo que todas essas bolas são "normais" também.
Portanto as únicas bolas que podem ser falsas são a 7 e a 8. Como constatamos na primeira pesagem que as bolas 5, 6, 7 e 8 são mais pesadas que as bolas 1, 2, 3 e 4, logo se apenas as bolas 7 e 8 podem ser falsas elas invariavelmente têm de ser mais pesadas que o normal, para satisfazer a primeira pesagem. Portanto basta pesar uma com a outra na 3ª vez para ver qual é a mais pesada e, conseqüentemente, a falsa
O mesmo raciocínio se aplicaria com as bolas 5, 6, 7 e 8 mais leves que as 1, 2, 3 e 4 na primeira pesagem, bastanto trocar na explicação acima "pesadas" por "leves".
Se houver outra dúvida terei prazer em explicar, pena que eu viajo amanhã, portanto tem de ser hoje...