Doze bolas e uma balança

Divida isto i npara três grupos de quatro, A1, A2, A3, A4; B1, B2 …; C1, C2 … Cada etapa aqui corresponde a uma pesagem.

• Pesar A contra B.
  • Se A> B, então pese A1, B1 e B2 contra B3 , B4 e C1.
    • Se os pesos forem iguais, então um de A2 … 4 é mais pesado; pesar A2 e A3. Se forem iguais, A4 é mais pesado. Se uma for mais pesada, a bola será a mais pesada.
    • Se o primeiro grupo for mais pesado, A1 é mais pesado ou B3-4 é mais leve. Compare B3 e B4; se forem iguais, A1 é mais pesado; se eles forem diferentes, o mais leve é a bola mais leve.
    • Se o primeiro grupo for mais leve, então B1 ou B2 é mais leve. Pese-as e veja.
  • Se A < B, renumere todas as bolas A em bolas B e execute o procedimento acima passos.
  • Se A = B, pese A1, A2, A3 contra C1, C2, C3
    • Se eles forem iguais, então pese A1 contra C4. Se A1 for mais leve, então C4 é a bola ímpar e é pesada. Se A1 for mais pesado, então C4 é a bola ímpar e é leve.
    • Se A for mais pesado que C, pese C1 contra C2. Se eles forem iguais, então C3 é a bola ímpar e é mais leve. Se eles não forem iguais, então a mais leve das duas bolas é a mais leve
    • Se A for mais leve que C, pese C1 contra C2. Se eles forem iguais, então C3 é a bola ímpar e é mais pesada. Se não forem iguais, a mais pesada das duas bolas é a mais pesada.

Podemos trabalhar de trás para frente a terceira etapa para ver, aproximadamente, por que isso funciona. Na terceira pesagem, as opções precisam ser reduzidas a duas ou três bolas. Isso significa que a segunda pesagem deve ser reduzida para duas ou três bolas possíveis.

Sabemos que a primeira etapa removerá 1/3 ou 2/3 das soluções possíveis, não importa o que você faça. Isso significa que, no caso de 1/3, você precisa dividir as possibilidades de 8 em um grupo de 3, um grupo de 3 e um grupo de 2. A partir disso, a terceira pesagem aponta para a bola ímpar. Como esse caso implica que um conjunto de bolas é mais pesado, em virtude de encontrarmos a bola ímpar, sabemos se é mais pesada ou mais leve, então, na verdade, não precisamos nos preocupar com esta informação.

No caso 2/3, você precisa reduzir as possibilidades em um grupo de 3 e um grupo de 1, o que é fácil de fazer intuitivamente. Como não sabemos o peso relativo da bola ímpar neste caso, as informações da terceira pesagem devem ser usadas para determinar se a bola é mais pesada ou mais leve.

Comentários

• Embora essa resposta esteja correta, eu esperava uma resposta que explicasse a estratégia por trás das escolhas dos itens a serem pesados.
• @JoeZ. I ‘ Acrescentamos algumas informações sobre como determinei essa resposta, embora ‘ não tenha certeza se poderia falar sobre uma solução geral para este problema. (Além disso, Para sua informação, eu ‘ editei minha resposta à sua outra pergunta.)
• O que você ‘ colocou é bem. Estava pensando em raciocinar mais do que em estratégia, pense nisso novamente.

Pronto é outra maneira de resolver esse problema, que não envolve nenhum tipo de ramificação condicional. Na verdade, é possível definir um cronograma de pesagem fixo com antecedência e ainda determinar qual bola é mais leve ou mais pesada em apenas 3 pesagens. Explicarei como a seguir.

A essência de problemas como esses é: quanta informação você pode obter do procedimento que tem permissão para realizar? Com cada pesagem, a balança pode inclinar para a esquerda, inclinar para a direita ou permanecer equilibrada.Isso dá a você um total de 3 ³ = 27 resultados possíveis e, neste caso, você precisa discernir 24 resultados deles (uma das 12 bolas é leve ou pesada, que é 12 × 2 = 24 ).

Portanto, precisamos começar a tediosa tarefa de mapear cada resultado em um resultado.

Uma das coisas que podemos notar imediatamente é que também há três estados em cada bola pode estar dentro durante cada pesagem – no lado esquerdo da balança, no lado direito da balança ou fora da balança. Naturalmente, isso mapeia para os estados da escala de uma forma que é intuitivamente análoga:

Se a bola ímpar for mais pesada …

• e a bola é colocada no lado esquerdo, a balança vai inclinar para a esquerda.
• e a bola é colocada no lado direito, a balança vai inclinar para a direita.
• e a bola é fora da escala, a escala permanecerá equilibrada.

Se a bola for mais leve, os dois primeiros casos são invertidos.

Existem 27 maneiras possíveis de colocar cada bola em todas as três pesagens, cada uma correspondendo a um resultado diferente se essa bola for a ímpar. Precisamos encontrar um arranjo de bolas onde cada conjunto possível de posições e seu inverso (para os casos pesados e leves) sejam distintos – então não duas bolas estão no mesmo lugar para todas as três pesagens.

Aqui está um arranjo preliminar que satisfaz a propriedade de distinção. Observe que nenhum arranjo possível aparece mais de uma vez em ambas as tabelas:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 L R 4 L R R L 5 L R R L 6 L R R L 7 L L R R 8 L L R R 9 L L R R 10 L L R R R L 11 L R L R L R 12 R L L L R R L = place it on the left R = place it on the right = leave it off 

Imediatamente, encontramos o problema de que não estamos colocando o mesmo número de bolas em cada escala. Se você tiver sete bolas de um lado e uma do outro, é claro que a escala vai inclinar para o lado com sete bolas (a menos que sua bola estranha seja ridiculamente pesada, mas não vamos nos divertir cenário). Portanto, precisamos inverter algumas dessas configurações para que estejamos colocando quatro de cada lado para cada pesagem. Com algumas tentativas e erros, podemos obter algo assim:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 R L 4 L R R L 5 R L L R 6 L R R L 7 R R L L 8 L L R R 9 L L R R 10 R R L L L R 11 R L R L R L 12 L R R R L L 

Portanto, nossa programação final de pesagem de bolas é a seguinte:

Weighing 1: 1 4 8 12 / 5 7 10 11 Weighing 2: 2 6 9 11 / 4 7 10 12 Weighing 3: 5 8 9 10 / 3 6 11 12 

E os resultados são interpretados da seguinte forma:

==L : 3L L== : 1H R== : 1L ==R : 3H L=L : 8H R=L : 5H =L= : 2H L=R : 5L R=R : 8L =LL : 9H LL= : 7L RL= : 4L =LR : 6H LLR : 10L RLL : 12L =R= : 2L LR= : 4H RLR : 11H =RL : 6L LRL : 11L RR= : 7H =RR : 9L LRR : 12H RRL : 10H = : scale balanced L : scale tipped to the left R : scale tipped to the right nL : ball n is light nH : ball n is heavy 

E assim, criamos um esquema de pesagem onde cada pesagem é completamente pré-determinada de antemão, que ainda consegue determinar qual bola é a ímpar e se é mais leve ou mais pesado.

Você pode perceber que não usamos LLL, RRR ou === em nossos arranjos.

Não podemos “usar LLL e RRR como um 13º par para uma 13ª bola, porque então acabaríamos tendo que colocar nove bolas na escala, e não há como fazer isso, já que nove é ímpar. provavelmente poderia usá-lo em lugar de um dos LLR/RRL pares, mas deixando LLL e RRR out faz uma simetria no gráfico de resultados que eu gosto.

No entanto, o que é interessante é que você pode ter uma 13ª bola que você nunca coloque em qualquer balança, e se sua balança se equilibrar nas três pesagens, a 13ª bola que você nunca pesou é a bola ímpar (embora você obviamente não possa dizer sem uma quarta pesagem se é mais leve ou mais pesada).

Comentários

• Então, basicamente, pode-se resolver isso com 13 bolas, se tivermos a bola de 14º etalon. Ótima resposta.
• Provavelmente até 14 bolas, onde a 14ª bola pode ser mais pesada, é solucionável, mas é mais difícil, provavelmente você pode ‘ t.

Algumas das respostas existentes para esta pergunta antiga são excelentes, mas há uma resposta famosa que Acho que merece menção aqui. Vem de um artigo na Eureka , a revista anual da sociedade de matemática de estudantes da Universidade de Cambridge, escrito por CAB Smith sob o pseudônimo de “Blanche Descartes”.

Possui dois recursos muito interessantes. A primeira é que é uma solução de “remoção de ramificações”: você não precisa mudar o que faz nas pesagens posteriores, dependendo dos resultados das anteriores. A segunda é que, depois de ver, é quase impossível esquecer.

A solução de Smith é escrita inteiramente em verso e inclui uma explicação de como tudo funciona, mas citarei apenas o resposta real. “F” aqui é nosso protagonista, Professor Felix Fiddlesticks, cuja mãe pediu-lhe ajuda com o quebra-cabeça. Fiz algumas mudanças insignificantes na formatação original.

F colocou as moedas em uma linha
E desenhou uma letra em cada uma,
Para formar as palavras: F AM NOT LICKED
(Um ideia em seu cérebro havia clicado.)

E agora sua mãe ele vai ordenar:
“MA, FAÇA / GOSTE DE MIM PARA / ENCONTRAR
FALSO / MOEDA!”

Cada uma das três linhas da injunção de F descreve uma pesagem.Depois de fazer todos eles, os resultados determinam com exclusividade qual moeda é falsa e de que maneira.

Comentários

• +1. Isso eu acho é uma versão embelezada da Joe Z ‘ resposta

Passei algum tempo trabalhando neste quebra-cabeça depois que ele apareceu em “Brooklyn Nine-Nine” (se quiser, você pode assistir o Capitão Holt descrever o quebra-cabeça aqui ) e escrevi uma solução detalhada e ilustrada aqui: Solução da Ilha de Tyreses . versão particular que estou tentando encontrar um ilhéu, Diffy, que seja mais pesado ou mais leve do que os outros 11 ilhéus.

Lições

A solução final leva em consideração duas coisas que aprendi com tentativas anteriores:

1. Em um grupo de quatro, posso identificar Diffy em duas pesagens.

   A. Primeiro, coloco dois ilhéus do grupo contra dois conhecido não-Dif fys. Se a gangorra se inclinar, sei que Diffy é um desses dois. Se a gangorra permanecer uniforme, sei que Diffy é um dos outros dois.

   B. Agora, eu seleciono um dos dois possíveis Diffys restantes e o coloco contra um não-Diffy conhecido. Se a escala se inclinar, encontrei Diffy. Se o tabuleiro permanecer empatado, sei que Diffy é o último ilhéu remanescente.

   C. Alternativamente, se a gangorra se inclinar na Etapa A e você quiser saber se o DIffy é pesado ou leve, você pode observar a direção da Etapa A e colocar os dois possíveis Diffys restantes na escala oposta um ao outro. Se a gangorra se inclina na mesma direção da etapa A, então Diffy é aquele que ainda está do mesmo lado que estava durante a etapa A. Caso contrário, se a orientação da gangorra mudar, Diffy está do outro lado.

2. Em um grupo de três posso identificar Diffy em uma pesagem, desde que tenha informações direcionais. Descreverei isso com mais detalhes no Uso # 3.

Solução

Por causa da lição nº 1, posso separar quatro ilhéus antes de verificar o resto. Se Diffy estiver naquele grupo de quatro, a primeira pesagem será igual, e agora posso identificá-lo entre os quatro com meus dois movimentos restantes. Se Diffy não estiver naquele grupo de quatro, agora tenho quatro ilhéus que posso descartar e também usar para tarar minha gangorra.

Então, para meu primeiro uso da gangorra, eu pesar os oito ilhéus restantes uns contra os outros, com quatro de cada lado.

Use # 1

Já esbocei meu plano se esse primeiro uso de gangorra for par, então o que vem a seguir se for estranho? É aqui que entra o gênio.

Agora tenho algumas “informações direcionais”. Doravante, chamarei qualquer direção que a gangorra inclinou no Uso 1 de “Direção 1 ″ ou“ D1 ″ para abreviar. Eu sei que se Diffy é pesado, ele está da parte da gangorra que desceu, e se Diffy é leve, ele está da parte da gangorra que subiu. Se eu mover Diffy, a gangorra mudará a orientação! Não há escolha porque Diffy, e apenas Diffy, faz com que a gangorra se incline. Além disso, lembre-se da lição nº 2, eu tenho informações direcionais e um movimento após o atual, então posso eliminar totalmente três Diffys possíveis antes do próximo uso da gangorra. Vou precisar usar um dos ilhéus que descartei no Uso 1 para manter três ilhéus de cada lado.

Uso # 2

Se o Uso # 2 nos dá uma gangorra, podemos encontrar Diffy nos três que removemos, mas se não, precisamos prestar atenção para a direção em que a gangorra se move. Ele se moveu da mesma maneira que antes, Direção 1, ou mudou a orientação para a Direção 2? Nossa próxima escolha será baseada na resposta! Se ele se moveu na Direção 1, sabemos que Diffy não é um dos ilhéus que trocou de lado para o Uso # 2. Se a gangorra se moveu na direção 2, então Diffy é um dos side-switchers. De qualquer maneira, nós o reduzimos a um de três ou dois. O uso # 3 é um pouco difícil de generalizar, pois é diferente para cada possibilidade.

Uso # 3

No caso em que tenho um grupo de três possíveis ilhéus – Diffy, dois desses ilhéus estavam do mesmo lado durante o Uso # 1, quando a gangorra mudou para D1. Se eu colocar um desses ilhéus em cada lado da gangorra e a gangorra se mover novamente para D1, saberemos que Diffy é o ilhéu do lado original. Se a gangorra se mover para D2, saberemos que Diffy está no lado oposto da gangorra. Se a gangorra permanecer estável, sabemos que Diffy é o terceiro membro do grupo.

Todos mapeados

Comentários

• Esta solução é falha para esta questão.É aceitável apenas se eles pedirem para identificar Diffy, mas não se ele é mais leve ou mais pesado (veja Even – Even – Even no seu diagrama, L não foi ponderado :)) Então, nesse caso, podemos resolver o quebra-cabeça com 13 pessoas.

Esta é uma reescrita de R. Allen Gilliam de A solução de Jared Anderson de outra versão deste quebra-cabeça neste site. Talvez seja apenas como minha mente funciona, mas parece muito mais fácil de entender.

Numere os homens (ou moedas ou bolas) de 1 a 12.
Pesa 1 2 3 4 contra 5 6 7 8.
Se eles são iguais, então o homem diferente é 9 10 11 ou 12. Vá para I abaixo.
Se forem diferentes, observe se 1 2 3 4 é mais pesado ou mais leve.

Pesar 1 2 3 5 contra 4 10 11 12. (Observe que sabemos que 10 11 e 12 não são diferentes.) Existem três possibilidades:
(1) Se 1235 tem o mesmo diferença (mais pesado ou mais leve) como 1234, então o diferente deve ser 1 2 ou 3 e tem a mesma diferença (mais pesado ou mais leve) que 1234. Passe para II abaixo.
(2) Se 1235 equilibra 4 10 11 12 , então o diferente deve ser 6 7 ou 8 (os que removemos) e tem a mesma diferença (mais pesado ou mais leve) que 5678. Passe para II abaixo.
(3) Se 1235 agora tem a diferença oposta (mais pesado ou mais leve) como 1234, então 4 ou 5 é o diferente. Ou 4 tem a mesma diferença que 1234 (mais pesado ou mais leve) ou 5 tem a mesma diferença que 5678 (mais pesado ou mais leve). Então, simplesmente pesamos 4 contra 1. Se eles forem iguais, então 5 é o diferente. Se eles forem diferentes, então 4 é o diferente.

I. Descobrir qual dos 9 10 11 12 é diferente com duas pesagens quando você não sabe se o diferente é mais pesado ou mais leve:

Pesar 9 contra 10. Duas possibilidades:
(1) Se eles “são diferentes, então tem que ser 9 ou 10. Pese 9 e 11. Se eles forem iguais, 10 é o diferente. Se eles forem diferentes, é 9.
(2) Se eles forem iguais, 10 é o diferente. “são iguais, então tem que ser 11 ou 12. Pese 9 e 11. Se eles forem iguais, 12 é o diferente. Se eles forem diferentes, é 11.
(Se for” s 12, não saberemos se ele era mais pesado ou mais leve, pois nunca o pesamos. Nós o encontramos por eliminação. Ele deve ser diferente, pois todos os outros têm o mesmo peso.)

II. Descobrir qual dos três homens é diferente com um pesando quando você sabe se o diferente é mais pesado ou mais leve:

Renomeie os três homens 1 2 3. Pesar 1 contra 2. Duas possibilidades:
(1) Se forem iguais, 3 é o diferente.
(2) Se forem diferentes, o que tiver a diferença correta rence (mais pesado ou mais leve) é o diferente.

Esta parece ser a solução mais simples para 12 itens se você só precisar encontrar o item de peso diferente, como algumas versões do quebra-cabeça pedem. A solução de Joe Z pode encontrar o item e a diferença com 12 itens, e o item diferente com 13 itens. Encontrar o item diferente e a diferença com 14 itens parece matematicamente impossível com 3 pesagens porque há apenas 27 resultados possíveis com 3 pesagens e há 28 possibilidades com 14 itens. Mas poderia uma variação da solução de Joe Z encontrar o item diferente de 13 e se ele é mais pesado ou mais leve? Em caso afirmativo, encontrar o diferente, mas não a diferença com 14 itens seriam possíveis. Encontrar o diferente, mas não a diferença entre 15 seria impossível, porque você pode deixar apenas um item fora das pesagens e ainda ser capaz de identificar o diferente, e se você pesar o item, você ” saber se é mais leve ou mais pesado, o que sabemos que é matematicamente impossível com 14 itens.

Esta solução é semelhante a o fornecido por R Gilliam, mas difere na segunda etapa. Divi de as bolas em 3 grupos de 4 bolas cada. Vamos chamá-los de g1 g2 e g3 escolher dois grupos quaisquer e pesá-los um contra o outro. Um dos dois cenários é verdadeiro. As bandejas estão equilibradas: as 8 bolas que você acabou de pesar têm o peso correto. As bandejas são desequilibradas: 4 bolas que você não pesou, todas têm o peso correto.

De qualquer forma, no final da primeira pesagem você tem pelo menos 4 bolas com o peso correto.

Para a segunda pesagem um lado da frigideira deve ter 3 bolas com o peso correto. Se as bandejas ficaram desequilibradas após a primeira pesagem, coloque 3 bolas de uma das bandejas não balanceadas na outra bandeja. Se as bandejas foram balanceadas após a primeira pesagem, coloque 3 dos 4 bolas que saíram da primeira pesagem para a outra panela.

Se as panelas ficarem desequilibradas após esta pesagem, você saberá se a bolinha é mais pesada ou mais leve, pois uma das panelas contém bolas do peso correto. Se as bandejas estiverem equilibradas, a 4ª bola que foi deixada de fora é a estranha e você pode descobrir se ela é mais pesada ou li pesar contra uma bola de peso correto.

Se as panelas estiverem desequilibradas, você saberá se o estranho é mais pesado ou mais leve. Pegue 2 das 3 bolas da assadeira (que não contém o peso correto das bolas) e pese-as uma contra a outra. Você já sabe se o estranho é mais pesado ou mais leve. Se as bandejas estiverem desequilibradas, escolha a bandeja que corresponde à direção do peso do estranho. se as bandejas estiverem equilibradas, a terceira bola é a estranha.

Você também pode resolvê-lo usando 4 grupos de 3 bolas . Pese 3 contra 3 e, se equilibrar, você pode manter essas 6 bolas de lado como iguais. Se eles não se equilibrarem, você sabe que a bola ímpar está naquele grupo de 6. Em seguida, pese 3 dos iguais conhecidos contra qualquer um dos 2 grupos de 3 incógnitas. Se equilibrar, o ímpar está na final grupo de 3. Se não houver equilíbrio, você sabe que o ímpar ainda está na escala. Por fim, utilizando o último grupo de 3 bolas desconhecidas e desiguais, coloque uma em cada ponta e reserve a terceira. Se a balança se equilibra, você sabe que a bola solitária que você deixou de lado é a bola ímpar. Se a escala não se equilibra, você sabe que a bola ímpar está na escala. Para determinar a bola ímpar e se ela é mais pesada ou mais leve, você precisa ter notado se o grupo desconhecido era mais pesado ou mais leve do que o igual conhecido grupos. Se fossem mais pesadas, a bola solitária é mais pesada.

Comentários

• ” Para determinar o bola ímpar e se ela ‘ é mais pesada ou mais leve, você precisa ter notado se o grupo desconhecido era mais pesado ou mais leve do que os grupos iguais conhecidos. ” Se todos os três grupos com os quais você pesou nas duas primeiras pesagens forem iguais, você não ‘ terá essas informações.

(1) Coloque as bolas 6 e 6 na escala. Remova um de cada lado até que a balança se equilibre.

(2) Pegue as duas últimas removidas (ou as duas restantes se a balança nunca estiver equilibrada) e coloque em um lado (lado A) e duas bolas com peso igual no outro (lado B). Se o lado A for inferior, o oddball será mais pesado; se o lado B for inferior, o oddball será mais leve. Remova um de cada lado. Se a balança se equilibra, a bola removida do lado A é a excêntrica, se não a bola restante do lado A é.

Comentários

• Isso requer a sete pesagens. O problema pede que você faça isso em três.
• @nosun – Bem-vindo ao puzzling.se. Só para você saber, as respostas incorretas às vezes são rejeitadas para ajudar a separá-las das boas respostas. Isso não tem a intenção de desencorajá-lo de fornecer boas respostas a outras perguntas.