Nosso recente conjunto de quebra-cabeças apresentava a humilde balança de dois pratos, historicamente um símbolo de comércio e governo, arte e ciência. As balanças de equilíbrio também são populares na matemática recreativa. Os quebra-cabeças de equilíbrio exigem raciocínio lógico e claro e se prestam bem à generalização matemática. Vamos ver como Quanta os leitores equilibraram essas qualidades nos quebra-cabeças abaixo.
Quebra-cabeça 1
Você tem oito moedas de aparência idêntica. Um é falsificado e mais leve que os outros, que possuem pesos idênticos. Encontre a moeda ruim em duas pesagens. Encontre a fórmula geral para o número máximo de moedas para as quais você pode encontrar a moeda falsa em x pesagens.
Lidar com uma versão simples de um problema geralmente revela a chave para a solução. Nesse caso, imagine que você tem apenas três moedas, sendo uma mais leve que as outras duas. Se você pesar qualquer um deles contra um dos outros dois, ou eles se equilibrarão ou não. Se não, você sabe qual é mais leve. Se eles se equilibrarem, então o terceiro é o mais leve. Você só precisa de uma única pesagem.
Portanto, neste quebra-cabeça, se você conseguir isolar um grupo de três (ou menos) contendo a moeda leve na primeira pesagem, precisará apenas de mais uma pesagem. Você pode fazer isso equilibrando quaisquer três contra quaisquer outros três. Se os dois grupos estiverem desequilibrados, você encontrou o grupo que contém o leve e pode proceder como acima para a segunda pesagem. Se eles se equilibrarem, basta pesar as duas moedas restantes uma contra a outra e você encontrará a mais leve.
Observe que isso também funciona se houver três no grupo sem peso, então poderíamos começar com nove moedas. Seguindo essa lógica, e começando com três moedas, para cada pesagem adicional podemos encontrar a moeda leve em três vezes o número de moedas que tínhamos anteriormente. A fórmula que nos dá o número máximo de moedas n in w pesagens é, portanto, n = 3w.
Quebra-cabeça 2
Você tem 12 moedas de aparência idêntica. Um é mais pesado ou mais leve que os outros, que têm pesos idênticos.
-
Encontre a moeda ruim em três pesagens.
-
Qual é o número máximo de moedas para as quais você pode encontrar a ruim em quatro pesagens? Descreva como você encontraria a moeda falsa.
A solução para este quebra-cabeça foi bem descrita por Ted, que também mostrou que você pode realmente detectar a moeda ruim entre 13 moedas em três pesagens. Aqui está a solução de Ted (com recuos para separar as três pesagens em cada caso):
Comece pesando 4 moedas contra 4 moedas.
Caso 1: Se desbalanceado, para a segunda pesagem coloque 2 de cada lado mais pesado em ambos os lados da balança junto com 1 de cada lado mais leve.
1a: Se desequilibrada, a moeda ruim são as 2 moedas ainda no lado pesado ou a única moeda ainda no lado leve.
Pese as 2 moedas pesadas possíveis, a ruim é a mais pesada das duas, ou a única leve se estiverem equilibradas.
1b: Se a segunda pesagem estiver balanceada, a moeda ruim é uma das 2 não utilizadas do lado mais leve da primeira pesagem.
Pese-os um contra o outro, o mais leve é ruim.
Caso 2: Se estiver balanceado, a moeda ruim é uma das 5 restantes. Pese 3 desses contra quaisquer 3 já pesados (que são conhecidos como bons).
Caso 2a: Se desbalanceada, você sabe que a moeda ruim é uma dessas 3 e se é leve ou pesada.
A terceira pesagem é qualquer 2 dessas umas contra as outras - se desbalanceada, isso identifica a moeda ruim, se balanceada é a última das três.
Caso 2b: Se a segunda pesagem for balanceada, a moeda ruim é uma das 2 restantes.
Pese qualquer um deles contra uma moeda boa conhecida. Se esse resultado for desequilibrado, essa nova moeda é ruim e você sabe se ela é pesada ou leve. Se este resultado for equilibrado, a 13ª moeda é ruim, mas não se sabe se é pesada ou leve (o que não precisamos saber, então pronto).
Ted também passou a mostrar que o número máximo de moedas para quatro pesagens é 40. A fórmula para este quebra-cabeça é: n = (3w − 1)/2.
Para os quebra-cabeças restantes, as fórmulas generalizadas ainda estão sob investigação por matemáticos profissionais e são objeto de artigos publicados, alguns dos quais foram citados por Rainer na primavera. Vou me limitar a soluções para o pequeno número de moedas que consideramos nos quebra-cabeças e mencionarei apenas generalizações que decorrem naturalmente dos métodos usados nesses casos.
Quebra-cabeça 3
Esta é uma variação do quebra-cabeça 1. Você novamente tem oito moedas de aparência idêntica, uma das quais é mais leve que as outras. No entanto, agora você tem três escalas. Duas das escalas funcionam, mas a terceira está quebrada e dá resultados aleatórios (às vezes está certo e às vezes errado). Você não sabe qual balança está quebrada. Quantas pesagens serão necessárias para encontrar a moeda leve?
Como vimos no problema 1, são necessárias apenas duas pesagens com uma boa balança. Também sabemos que as duas balanças boas sempre concordarão, portanto, se apenas repetirmos cada pesagem nas três balanças, teremos a resposta em seis pesagens, conforme sugerido pelo leitor. Se tentarmos fazer em um número menor de pesagens, fica um pouco complicado. Não podemos identificar uma boa balança apenas pesando as mesmas moedas em duas balanças, porque mesmo que elas concordem, qualquer uma das duas ainda pode ser uma balança ruim. (Isso também mostra a facilidade com que informações erradas ou aleatórias podem ofuscar a verdade.)
Na verdade, este problema pode ser resolvido, de forma muito inteligente, em apenas quatro pesagens! Rainer na primavera postou a solução usando uma notação nova que parece ter sido criada para este quebra-cabeça. Mas antes de ir lá, quero que você imagine um cenário que, espero, tornará as coisas mais intuitivas.
Imagine que você é um detetive investigando um atropelamento em um pequeno país cujos carros têm placas de dois dígitos usando apenas os dígitos 0, 1 e 2. Três pessoas, A, B e C, observaram o incidente. Dois deles sempre respondem corretamente a uma pergunta de três opções, e um dá respostas completamente aleatórias. Você não sabe quem é o respondente aleatório. Você deve fazer a cada um deles uma única pergunta de três opções e, em seguida, escolher aquele que está definitivamente dizendo a verdade para obter mais informações.
Aqui está como você faz isso. Pergunte a A se o primeiro dígito é 0, 1 ou 2. Digamos que A diga 2. Pergunte a B se o segundo dígito é 0, 1 ou 2. Digamos que B diga 1. Então peça a C para fazer uma escolha entre estas três afirmações:
- Apenas A está dizendo a verdade.
- Apenas B está dizendo a verdade.
- Ambos estão dizendo a verdade.
Você pode acreditar naquele que C lhe disser e questionar essa pessoa sobre o outro dígito. Para ver por que, considere que se A está mentindo, então C é confiável e dirá que B está dizendo a verdade. O segundo dígito será de fato 1 e você pode então questionar B sobre o primeiro dígito. Da mesma forma, se B está mentindo, então C é novamente confiável e dirá que A está dizendo a verdade. Então o primeiro dígito é de fato 2 e você pode questionar A sobre o segundo dígito. Finalmente, se C está mentindo, então tanto A quanto B são confiáveis, então você ainda pode acreditar e escolher quem C disser. (E se C diz que A e B estão dizendo a verdade, então ambos devem estar.) A chave aqui é que sua escolha de perguntas não permite que C minta de forma a lançar dúvidas sobre A e B. Como pelo menos um de A e B deve ser confiável, você sempre pode escolher aquele com o qual C concorda, mesmo que seja apenas uma resposta aleatória. Se todos os três concordarem, você já tem os dois dígitos da placa.
Veja como traduzir esse conto de volta ao nosso quebra-cabeça. As escalas são A, B e C. Você pode traduzir os dois dígitos da placa para as moedas da seguinte forma: 01 é a moeda 1, 02 é a moeda 2, 10 é a moeda 3, 11 é a moeda 4, 12 é a moeda 5, 20 é a moeda 6, 21 é a moeda 7 e 22 é a moeda 8. Leitores astutos reconhecerão que este é o sistema numérico de base 3 (ou ternário). Observe também que há um número adicional possível 00, que você pode usar para uma nona moeda para a qual essa técnica também funcionará, como no quebra-cabeça 1.
Para a primeira pesagem, você divide as moedas pelo primeiro dígito (base 3), então seus três grupos serão moedas [1, 2], [3, 4, 5] e [6, 7, 8]. Pese [3, 4, 5] contra [6, 7, 8] na escala A. Se A estiver funcionando bem, você terá o grupo correto do primeiro dígito como no quebra-cabeça 1. Da mesma forma, para a segunda pesagem na escala B, seus grupos serão aqueles com o mesmo segundo dígito: [1, 4, 7], [2, 5, 8] e [3, 6]. Se B estiver funcionando bem, você terá o segundo dígito correto. Para a terceira pesagem, na escala C, você pesa o grupo que A identificou contra o grupo que B fez. Seguindo nosso exemplo, para 21, os grupos serão [6, 7, 8] e [1, 4, 7]. A moeda 7 não pode ser colocada em ambos os lados ao mesmo tempo, então a deixamos de fora e pesamos [6, 8] e [1, 4] um contra o outro. Note que se A e B são ambos confiáveis, então 7 é de fato a resposta correta, e não importa qual lado sai mais claro em C. Se por acaso a pesagem em C estiver balanceada, então todas as três balanças concordam, e você tem sua resposta (moeda 7) em apenas três pesagens. Se A é confiável e B não, a moeda mais leve está em [6, 8], qual escala C irá confirmar, e se B for confiável e A não, a moeda mais leve está em [1, 4], qual escala C também irá confirmar.
Assim, em três pesagens, identificamos a moeda leve ou a reduzimos a um grupo de duas, e também identificamos uma balança de trabalho. A quarta pesagem na balança A ou B (qualquer que seja a balança C acordada) fará o resto.
Esta solução parece-me incrivelmente bonita!
Este método pode ser generalizado para encontrar a moeda leve entre 32x moedas em 3x + 1 pesagem com o conjunto de balanças fornecido. Assim, você precisa de sete pesagens para 81 moedas. Para números maiores de moedas (>~1,000), uma solução ainda mais forte existe.
Quebra-cabeça 4
Você tem 16 moedas, oito das quais são pesadas e do mesmo peso. Os outros oito são leves e do mesmo peso. Você não sabe quais moedas são pesadas ou leves. As moedas parecem idênticas, exceto por uma que possui marcações especiais. Com uma boa balança, você consegue descobrir se a moeda especial é leve ou pesada em três pesagens? Qual é o número máximo de moedas com as quais você pode começar e resolver esse problema com sucesso em quatro pesagens?
À primeira vista, esse quebra-cabeça parece quase impossível de ser feito em três pesagens, como concluiu um de nossos leitores. No entanto, com alguma esperteza isso pode ser feito, e ambos Ted e Rainer na primavera forneceu soluções corretas. Ted forneceu alguns princípios gerais inestimáveis aos quais vale a pena prestar atenção.
Primeiro, até obter um resultado desbalanceado de uma pesagem, você não terá informações suficientes para determinar se a moeda especial é pesada ou leve. Então você tem que tentar forçar um resultado desequilibrado.
Segundo, se você obtiver um resultado balanceado (digamos, a moeda especial A equilibra a moeda B), você pode combinar as moedas que estão balanceadas e pesá-las contra mais duas moedas, C e D. Se elas estiverem desbalanceadas, você tem a resposta; caso contrário, você dobrou o número de moedas semelhantes, o que pode ajudá-lo a obter uma resposta desequilibrada na próxima pesagem. Você também pode realizar este processo ao contrário com números de moedas que são potências de dois (4, 8, etc.) se você tiver um resultado inicial desbalanceado como visto na solução a seguir.
Abaixo está todo o procedimento que pode identificar o tipo da moeda especial A em todos os casos em três pesagens. (B, C e D são três moedas colocadas do mesmo lado que A no peso 1 (W1); X e Y são as duas moedas não usadas em W1.)
Este quebra-cabeça foi inventado pelo matemático russo Konstantin Knop, uma autoridade mundial em quebra-cabeças de pesagem de moedas. Muitos de seus trabalhos estão em russo, mas você pode encontrar vários quebra-cabeças de moedas (entre outros quebra-cabeças interessantes) no blog de sua colaboradora Tanya Khovanova.
Quanto à generalização, deixo para você ver se esse mesmo método funciona para encontrar o tipo de uma moeda especial entre 32 moedas, das quais 16 são pesadas e 16 leves.
Quebra-cabeça 5
Você tem n moedas de aparência idêntica, algumas das quais são falsificadas e mais leves que as outras. Tudo o que você sabe é que há pelo menos uma moeda falsificada e que há mais moedas normais do que falsificadas. Seu trabalho é detectar todas as moedas falsas.
O fato de haver pelo menos uma moeda leve e de haver mais moedas normais do que leves torna esse quebra-cabeça menos complexo do que parece à primeira vista, pelo menos para números pequenos. Vejamos os números de pesagens de uma a oito moedas.
Para uma e duas moedas, não pode haver moedas leves na segunda condição, portanto, não são necessárias pesagens.
Três moedas: Apenas uma moeda leve. Uma pesagem necessária por quebra-cabeça 1.
Quatro moedas: Apenas uma moeda leve. Uma pesagem adicional necessária, então w = 2.
Cinco moedas: Uma a duas moedas leves. Este é o primeiro caso interessante. A questão é: devemos pesar uma moeda contra uma, ou duas moedas contra duas?
Se pesarmos um contra um, podemos ter:
- Duas pesagens desequilibradas: Duas moedas descobertas; acabamos.
- Uma pesagem balanceada de duas: As moedas balanceadas têm que ser normais, então a última moeda precisa de outra pesagem, w = 3.
- Duas pesagens balanceadas: Na terceira pesagem, pese uma moeda de cada pesagem anterior contra outra. Se estiverem equilibrados, todos os quatro são normais e a moeda 5 é a mais leve. Acabamos; w = 3 novamente. Se estiverem desequilibradas, encontramos as duas moedas leves e terminamos em três pesagens.
Se, em vez disso, pesarmos dois contra dois, ainda precisamos de três pesagens, porque temos que distinguir entre as possibilidades de que as moedas sejam diferentes ou semelhantes em ambos os lados. Pesagens com pequenas quantidades de moedas agrupadas não parecem ter nenhuma vantagem sobre pesagens com moedas individuais.
Isso é comprovado para:
Seis moedas: Uma a duas moedas leves; w = 4.
Sete moedas: Uma a três moedas leves; w = 5.
Oito moedas: Uma a três moedas leves; w = 6. Esta solução tem uma estrutura simples:
- Primeiro faça quatro pesagens de uma moeda contra a próxima. Todas as moedas são usadas.
- Pior caso: Todas as quatro pesagens são balanceadas (há duas moedas leves que se equilibram).
- Próximas duas pesagens: Pese uma moeda de 1 contra uma moeda de 2; da mesma forma, pese uma moeda de 3 contra uma moeda de 4.
- Uma dessas pesagens será desbalanceada, identificando as duas moedas leves. Terminamos em seis pesagens.
Desculpe, nossa sequência de 0, 0, 1, 2, 3, 4, 5, 6 certamente não é interessante o suficiente para ser submetida ao Enciclopédia On-Line de Sequências Inteiras!
As Jonas Togersen Kjellstadli apontada, a solução parece ser w = n − 2 para números pequenos, mas não provamos que isso não mudará para números maiores. Em algum n, o uso de várias pesagens de moedas pode começar a fazer melhor ou mais pesagens do que n − 2 podem ser necessários. Podemos simplesmente generalizar a solução para oito moedas para todas as potências de 2, dando n − 2 como o limite superior para o número de pesagens para todas as potências de 2.
Mark Pearson discutiu a semelhança desse problema com os códigos de correção de erros e sugeriu o uso de uma abordagem de teoria da informação baseada no número de resultados possíveis. Usando tal abordagem, Mike Roberts postou um limite inferior para o caso mais geral, que Rainer na primavera derivou uma aproximação para. Rainer também postou limite superior de um artigo publicado, mas observou que os limites não são nítidos para n e, portanto, não é útil para os pequenos números que consideramos acima. Assim, para sete moedas, os limites citados dão um intervalo de 4 a 16, no qual nossa resposta, 5, fica entre. J. Payette fornece referências matemáticas adicionais e limites para todos os quebra-cabeças.
Obrigado a todos que participaram. O prêmio Insights deste mês vai para Ted e Rainer aus dem Spring. Parabéns!
Até a próxima para novas Insights.
