In partnership with

ED 065

Você escolhe a edição de amanhã: a votação está no fim desta edição.

Os 5 palpites de Knuth que acham qualquer senha

Knuth provou em 1977 que as 1.296 senhas do Mastermind caem em cinco jogadas, desde que cada uma encolha o pior grupo que sobra.

Tabuleiro de Mastermind com quatro pinos coloridos escondidos e pinos de resposta.

A senha escondida e os pinos de resposta

▼

Quantos palpites bastam para descobrir qualquer senha do Mastermind? Cinco, contando a jogada que acerta. A prova tem autor e data: Donald Knuth fez a conta e publicou o resultado em 1977.

O jogo cabe numa caixa pequena. Um jogador esconde atrás de uma tampa uma fileira de quatro pinos coloridos, escolhidos entre seis cores, com repetição liberada. O outro tenta adivinhar a fileira escondida, que todo mundo chama de senha.

A cada palpite, o dono da senha devolve pinos pequenos de resposta. Um pino preto para cada cor certa na casa certa; um pino branco para cada cor certa na casa errada. A resposta diz quantos acertos houve, nunca quais.

Seis cores em quatro casas dão 6 × 6 × 6 × 6 combinações: 1.296 senhas possíveis. Quem joga pela primeira vez costuma chutar quatro cores diferentes, recebe dois brancos e sente que avançou.

Avançou pouco. Dois brancos deixam centenas de senhas ainda vivas, e o iniciante não sabe quantas. Ele escolhe a jogada seguinte pela que parece promissora, e costuma perder a partida justamente nessa escolha.

Knuth trocou a pergunta. Em vez de procurar a jogada que pode acertar, procurou a que deixa o pior cenário menor. Cada palpite reparte as senhas restantes em grupos, um grupo para cada resposta possível.

O que importa é o tamanho do maior grupo, porque a senha escondida pode estar justamente nele. Um palpite bom deixa grupos parecidos entre si; um palpite ruim deixa um grupo gordo e vários vazios.

Com essa regra, o primeiro palpite ideal repete duas cores em pares, algo como azul, azul, vermelho, vermelho. Parece desperdício de casas, e rende mais que quatro cores distintas.

A seguir: quem inventou o jogo e como o professor de Stanford fez a conta, um enigma para resolver de lápis na mão e a solução, com o motivo de o par repetido vencer.

Continue lendo ↓

Quem banca a edição de hoje

You're invited to the world's largest virtual email marketing conference.

Become an email marketing GURU for FREE.

GURU Conference, powered by Constant Contact, is back November 12–13. It's 100% virtual and 100% free, and it's packed with tactics you can use right away on newsletters, deliverability, design trends, AI, and what NOT to do with email.

What to expect:

Speakers including Molly Ringwald, Dan Levy, Amy Porterfield, Frank Vella + more
Sessions from world-class marketers at top brands
Networking every day
DJs, world-record breaking, and an alarming amount of rom-com fun!

Last year, 29,000+ marketers joined us. This year is even bigger, and spots are limited.

Save Your Spot!

Patrocinadores mantêm a edição gratuita

I A resposta de ontem

Do correio de Israel para Stanford

Mordecai Meirowitz, funcionário dos correios e técnico de telecomunicações em Israel, criou o Mastermind em 1970. Ele adaptou um jogo antigo de lápis e papel, Touros e Vacas (Bulls and Cows, no original em inglês), em que se adivinha um número de quatro algarismos em vez de cores.

Os grandes fabricantes recusaram a ideia. A pequena Invicta Plastics, de Leicester, na Inglaterra, comprou o projeto e lançou o tabuleiro em 1971, com pinos coloridos, pinos de resposta e a tampa que esconde a senha. O jogo se espalhou pela Europa e pelos Estados Unidos na década seguinte.

Donald Ervin Knuth, professor de ciência da computação da Universidade Stanford e autor da série The Art of Computer Programming (A Arte da Programação de Computadores), olhou para o tabuleiro como um problema de busca. Publicou o artigo The Computer as Master Mind (O Computador como Mastermind) no Journal of Recreational Mathematics, volume 9, na edição de 1976 para 1977.

O método dele é braçal e exato. O computador lista as 1.296 senhas. Para cada palpite candidato, testa todas as senhas ainda vivas e conta quantas dariam cada resposta. Depois guarda só o tamanho do maior grupo.

Vence o palpite cujo maior grupo é o menor de todos. Matemáticos chamam essa escolha de minimax (minimizar o máximo, ou seja, tornar o pior caso o menor possível). Knuth aplicou a regra jogada após jogada, até sobrar uma senha só.

O resultado: nenhuma senha exige mais de cinco palpites. Na média das 1.296 senhas, a estratégia de Knuth acerta em 4,476 jogadas, segundo a tabela publicada no próprio artigo de 1977.

O melhor palpite de Knuth é o que encolhe o pior grupo que pode sobrar.

O limite que ficou de pé

Cinco jogadas é o melhor garantido, e a busca de Knuth mostrou que nenhuma estratégia desce para quatro em todas as senhas. Algumas sempre precisam do quinto palpite, qualquer que seja a abertura.

A média, por sua vez, ainda tinha folga. Em 1993, os pesquisadores Kenji Koyama e Tony W. Lai, num artigo do Journal of Recreational Mathematics, rodaram uma busca completa e chegaram a 4,340 palpites por senha. O preço dessa média menor é aceitar que uma senha rara peça seis jogadas.

A troca mostra que as duas metas brigam. Knuth protege o pior caso; Koyama e Lai protegem a média. O jogador escolhe qual perda tolera.

II O Enigma do dia

Três aberturas na mesa

Seis cores, quatro casas, 1.296 senhas. Compare três primeiros palpites: quatro pinos da mesma cor (1111), dois pares (1122) e quatro cores diferentes (1234). Primeira pergunta: se a resposta vier vazia, sem preto nem branco, quantas senhas sobram em cada caso? Segunda: qual dos três deixa o pior grupo menor? Terceira: por que quatro cores diferentes perdem, se testam mais cores de uma vez?

Numere as cores de 1 a 6 e trabalhe com algarismos: fica mais rápido que desenhar pinos. Uma senha como 3516 quer dizer verde, roxo, azul, laranja, conforme a ordem que você combinar.

Anote cada resposta como um par de números: pretos primeiro, brancos depois. Assim, 0 e 2 quer dizer nenhum preto e dois brancos. São 14 respostas possíveis, contando a vazia e a vitória com quatro pretos.

A primeira pista vale para a resposta vazia. Resposta vazia significa que nenhuma cor do palpite aparece na senha. Conte quantas cores sobram para cada casa e multiplique as quatro casas.

A segunda pista vale para o 1111. Ele só pergunta por uma cor. Pense no que acontece com todas as senhas que não têm a cor 1 e veja se o grupo delas é grande.

A terceira pista vale para o 1234. A resposta vazia quase nunca sai, porque sobram só duas cores. O grupo gordo mora nas respostas com um ou dois brancos, onde muitas senhas diferentes devolvem o mesmo sinal.

A quarta pista vale para o 1122. Ele pergunta por duas cores e ainda testa a posição de cada par. Repare que ele cobre menos cores que o 1234 e mesmo assim reparte melhor.

Onde o raciocínio escorrega

A primeira armadilha é contar cores testadas. Testar quatro cores parece render o dobro de testar duas, mas o que vale é como as senhas se espalham pelas respostas.

A segunda é olhar só a resposta vazia. Ela decide o caso do 1111, mas no 1234 o pior grupo vem de outra resposta. Compare sempre o maior grupo de cada palpite.

A terceira é achar que o melhor palpite precisa poder acertar. O 1122 raramente é a senha; ele vale pela informação que devolve.

O palpite que testa mais cores pode ser o que mais deixa senhas juntas.

Responda por escrito: as três contagens da resposta vazia, o maior grupo de cada palpite e o motivo de os dois pares vencerem.

Quem banca a edição de hoje

Tired of news that feels like noise?

Every day, 4.5 million readers turn to 1440 for their factual news fix. We sift through 100+ sources to bring you a complete summary of politics, global events, business, and culture — all in a brief 5-minute email. No spin. No slant. Just clarity.

Join for free today!

Patrocinadores mantêm a edição gratuita

III Sequência

O par repetido vence

Resposta vazia no 1111: sobram as senhas sem a cor 1, 5 × 5 × 5 × 5, ou seja, 625. No 1122: sobram as senhas sem 1 e sem 2, 4 × 4 × 4 × 4, ou seja, 256. No 1234: sobram as senhas feitas só de 5 e 6, 2 × 2 × 2 × 2, ou seja, 16.

O 1234 parece vencer, mas o pior grupo dele mora em outra resposta e tem 312 senhas, segundo a tabela de Knuth. O 1111 tem pior grupo de 625. O 1122 fica com 256, o menor dos três. Knuth abre com dois pares por causa dessa conta.

O motivo está na repartição. Quatro cores diferentes empurram muitas senhas para as mesmas respostas de um ou dois brancos. Os pares separam melhor, porque o branco e o preto de cada par dizem algo também sobre a posição.

A estratégia completa segue quatro passos, repetidos a cada jogada.

1. Liste todas as senhas que ainda batem com todas as respostas recebidas.

2. Para cada palpite possível, conte quantas dessas senhas dariam cada resposta.

3. Anote o maior grupo de cada palpite e escolha o palpite cujo maior grupo é o menor; no empate, prefira um palpite que ainda possa ser a senha.

4. Jogue, receba a resposta e descarte as senhas que não batem com ela.

Depois do 1122, o pior grupo tem 256 senhas. O segundo palpite de Knuth reduz qualquer grupo a no máximo algumas dezenas; o terceiro, a poucas unidades; o quarto deixa no máximo uma dúvida curta, e o quinto acerta.

O raciocínio vale fora do tabuleiro. Num jogo de adivinhar palavras, num teste de defeito em máquina ou numa triagem médica, a melhor pergunta é a que deixa o pior caso menor, mesmo que ela não possa acertar de primeira.

Quando a resposta pode cair em vários grupos, jogue para encolher o maior deles.

A Sequência é o placar de quem fecha sozinho. Um ponto por enigma resolvido antes de conferir a solução, e o placar zera quando você espia fora da hora.

“Com oito cores em vez de seis, qual abertura você testaria primeiro?”

Teste hoje: jogue uma partida de papel com alguém que esconda uma senha de quatro algarismos de 1 a 6. Abra com 1122 e, a cada resposta, anote a jogada. O esperado é acertar até o quinto palpite; se passar disso, reveja a contagem do maior grupo na jogada em que travou.

Quiz da edição

No teste dos três primeiros palpites do Mastermind (uma cor repetida quatro vezes, quatro cores diferentes, dois pares de cores), qual deles deixa o pior grupo de senhas restantes com o menor tamanho?

A1111, quatro pinos da mesma cor, com pior grupo de 625 senhas

B1234, quatro cores diferentes, com pior grupo de 312 senhas

C1122, dois pares de cores, com pior grupo de 256 senhas

DOs três empatam, porque o pior grupo depende só da resposta vazia

Veja o ranking de quem mais acerta →

Sua avaliação

Como foi a edição de hoje?

🧩🧩🧩🧩🧩 ótima 🧩🧩🧩🧩 boa 🧩🧩🧩 ok 🧩🧩 ruim 🧩 péssima

Escolha a edição de amanhã

Qual edição você quer ver amanhã?

Voto aberto até 11/10, 15h30

Sequência de De Bruijn