Doze moedas, três pesagens e nenhuma sorte: a Matemática garante encontrar a falsa

Uma moeda tem peso diferente das outras onze. Você não sabe se ela é mais pesada ou mais leve e só pode utilizar uma balança três vezes. O problema parece exigir sorte, mas sua solução revela uma conexão surpreendente entre Lógica, Matemática e Teoria da Informação.

Imagine doze moedas aparentemente idênticas. Onze possuem exatamente o mesmo peso. Uma é falsa, mas você não sabe qual, nem se ela é mais pesada ou mais leve. Você dispõe de uma balança de dois pratos e apenas três pesagens. Ao final, precisa identificar a moeda falsa e dizer se ela pesa mais ou menos. Parece impossível? Existe uma estratégia que garante a resposta em todos os casos.

Quantas possibilidades precisamos eliminar?

Existem doze moedas e cada uma pode ser mais pesada ou mais leve. São, portanto, 12 × 2 = 24 hipóteses. A moeda 3 mais pesada é uma hipótese diferente da moeda 3 mais leve. Uma solução precisa distinguir todas elas.

Uma balança oferece três respostas

Uma pesagem pode indicar prato esquerdo mais pesado, prato direito mais pesado ou equilíbrio. Três pesagens produzem, no máximo, 3³ = 27 sequências de resultados. Como temos 24 hipóteses, existe capacidade informacional suficiente. Mas essa contagem não prova, sozinha, que uma estratégia funciona: precisamos construí-la.

A primeira pesagem

Numere as moedas de 1 a 12. Coloque 1, 2, 3 e 4 no prato esquerdo; 5, 6, 7 e 8 no direito. Deixe 9, 10, 11 e 12 fora. Se houver equilíbrio, a falsa está entre 9 e 12, e as oito moedas pesadas são verdadeiras. Se a esquerda pesar mais, uma entre 1 e 4 é mais pesada ou uma entre 5 e 8 é mais leve. Se a direita pesar mais, as possibilidades se invertem. Em qualquer caso, restam exatamente oito hipóteses.

Quando a primeira pesagem termina equilibrada

A falsa está entre 9, 10, 11 e 12. Na segunda pesagem, compare 9, 10 e 11 com 1, 2 e 3, que sabemos serem verdadeiras. Se as três suspeitas pesarem mais, uma delas é falsa e mais pesada. Compare 9 e 10 na terceira pesagem: a mais pesada será falsa; se houver equilíbrio, será a 11. Se as suspeitas pesarem menos, proceda da mesma forma, procurando a mais leve. Se a segunda pesagem equilibrar, a falsa é a 12; compare-a com uma moeda verdadeira na terceira para saber se é mais pesada ou mais leve.

Quando a primeira pesagem fica desequilibrada

Suponha que a esquerda tenha ficado mais pesada. As hipóteses são 1, 2, 3 ou 4 mais pesadas, ou 5, 6, 7 ou 8 mais leves. As moedas 9 a 12 são verdadeiras. Na segunda pesagem, compare 1, 2 e 5 (esquerda) com 3, 6 e 9 (direita).

Se a esquerda pesar mais: as possibilidades são 1 mais pesada, 2 mais pesada ou 6 mais leve. Na terceira pesagem, compare 1 e 2: a mais pesada é falsa; se equilibrar, a falsa é a 6, mais leve.

Se a direita pesar mais: as possibilidades são 3 mais pesada ou 5 mais leve. Compare 3 com 9: se 3 pesar mais, é falsa; se equilibrar, a falsa é 5, mais leve.

Se equilibrar: as possibilidades são 4 mais pesada, 7 mais leve ou 8 mais leve. Compare 7 e 8: a mais leve é falsa; se equilibrar, a falsa é 4, mais pesada.

Se a primeira pesagem tivesse indicado a direita mais pesada, usamos a mesma segunda pesagem e invertemos as hipóteses de peso. Por exemplo, se a segunda também indicar a direita mais pesada, restam 1 mais leve, 2 mais leve ou 6 mais pesada: comparar 1 e 2 resolve. Se a segunda indicar a esquerda mais pesada, restam 3 mais leve ou 5 mais pesada: comparar 3 com 9 resolve. Se equilibrar, restam 4 mais leve, 7 mais pesada ou 8 mais pesada: comparar 7 e 8 resolve. Assim, todos os 24 casos são distinguidos.

O que acabamos de construir?

Uma árvore de decisão. Cada pesagem representa um nó; cada resultado, um caminho; e cada caminho conduz a um conjunto menor de hipóteses. O objetivo é que cada folha identifique uma única situação. Essa estrutura aparece em algoritmos de busca, diagnósticos e classificação. Em Trocar ou não trocar? O problema das três portas, a informação também altera o conjunto de possibilidades; aqui, podemos planejar quais informações obter.

A quantidade de informação pode ser calculada

Se existem N hipóteses igualmente prováveis, a informação necessária para identificar uma delas é log₂(N) bits. Para 24 hipóteses, log₂(24) ≈ 4,585 bits. Uma pesagem com três resultados equiprováveis oferece no máximo log₂(3) ≈ 1,585 bits; três pesagens oferecem até 4,755 bits. A pequena diferença mostra por que a estratégia precisa ser cuidadosamente organizada. A expressão da entropia pressupõe probabilidades especificadas: a contagem 3³, por si só, não exige que os resultados sejam equiprováveis.

Essa conexão com surpresa e informação também aparece em Uma mentira pode carregar mais informação que a verdade?.

Mas por que não conseguimos resolver treze moedas?

Treze moedas produziriam 26 hipóteses, menos que as 27 sequências possíveis de três pesagens. Parece viável, mas não é, se não houver uma moeda verdadeira adicional conhecida. Suponha que na primeira pesagem comparemos k moedas de cada lado. Se houver desequilíbrio, restam 2k hipóteses, que devem caber nas nove sequências de duas pesagens: 2k ≤ 9, logo k ≤ 4.

Se houver equilíbrio, a falsa está entre as 13 − 2k moedas não pesadas, cada uma podendo ser mais pesada ou mais leve. Restam 2(13 − 2k) hipóteses, que também precisam caber em nove resultados: 2(13 − 2k) ≤ 9, logo k ≥ 5. A contradição prova a impossibilidade. Contar resultados é necessário, mas não suficiente: as restrições físicas da balança também importam.

A diferença entre informação e conhecimento

A balança nunca diz diretamente qual moeda é falsa. Ela oferece uma comparação, que só adquire significado dentro de uma estrutura de hipóteses. Uma pesagem pode ser muito informativa ou quase inútil. Tudo depende da pergunta. Em Como três crianças descobrem um segredo porque ninguém respondeu?, o silêncio transmite informação porque os participantes conhecem as regras e raciocinam sobre o conhecimento dos demais. Aqui, a informação está na balança, mas a lógica de interpretação é igualmente decisiva.

O poder de fazer a pergunta certa

Com milhares de pesagens aleatórias, podemos desperdiçar tempo repetindo comparações. Com apenas três comparações planejadas, resolvemos o problema completamente. Resolver problemas não significa necessariamente executar mais operações; frequentemente significa organizar melhor as possibilidades. Antes de procurar uma resposta, precisamos descobrir qual pergunta elimina mais incertezas.

Se três perguntas bem construídas revelam aquilo que dezenas de perguntas aleatórias talvez não descubram, quantas dificuldades enfrentamos não por falta de informação, mas porque ainda não aprendemos a perguntar?

Livro recomendado

O Homem que Calculava, de Malba Tahan (Júlio César de Mello e Souza), reúne problemas e narrativas sobre o poder do raciocínio matemático. A obra é adequada ao tema, embora não seja um tratado de Teoria da Informação. Consultar a edição na Amazon Brasil (link afiliado; preço e estoque sujeitos a confirmação).

Referências

University of Cambridge, NRICH, problemas de pesagens; Wolfram Demonstrations Project, The 12 Coin Weighing Problem; fundamentos de árvores de decisão e Teoria da Informação.