Matemática do jogo de palavras: contagem, probabilidade e bits

Jogos de adivinhar palavras de cinco letras em seis tentativas viraram hábito diário de muita gente, e a pergunta “qual é a melhor primeira palavra?” aparece em toda roda de conversa. Por trás dela há matemática séria: contagem, probabilidade e teoria da informação. Neste texto usamos o jogo só como ponto de partida para aprender essas três ideias, que servem muito além dele. As listas e os números dos exemplos são hipotéticos, escolhidos para deixar as contas limpas.

Contagem: quantas palavras de cinco letras existem?

Comece pelo princípio multiplicativo: se uma escolha tem $a$ opções e outra, independente, tem $b$ opções, o par tem $a \cdot b$ possibilidades. Uma sequência de cinco letras, com o alfabeto de 26 letras e repetição permitida, tem 26 opções em cada posição.

26 \cdot 26 \cdot 26 \cdot 26 \cdot 26 = 26^5 = 11\,881\,376

Sequências de cinco letras com repetição permitida (princípio multiplicativo).

Se as cinco letras precisarem ser todas diferentes, a primeira posição tem 26 opções, a segunda 25, e assim por diante. Isso é um arranjo simples de 26 elementos tomados 5 a 5.

A_{26,5} = \frac{26!}{21!} = 26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 = 7\,893\,600

Sequências de cinco letras sem repetir letra.

Quase nenhuma dessas sequências é palavra de verdade. A lista de respostas possíveis de um jogo desse tipo tem da ordem de alguns milhares de palavras, uma fração minúscula das 11,9 milhões de sequências. É por isso que o jogo é possível: a linguagem já elimina quase tudo antes da primeira tentativa.

Outra contagem útil: cada casa do retorno do jogo recebe uma de três cores (letra certa no lugar certo, letra presente em outro lugar, letra ausente). Com cinco casas, são $3^5$ = 243 padrões de cores possíveis. Na prática, alguns padrões nunca ocorrem, mas 243 é o teto de quantos grupos um único palpite consegue criar.

Probabilidade: a chance de acertar no chute

Se restam N palavras candidatas e todas são igualmente prováveis, a probabilidade de acertar escolhendo uma delas ao acaso é 1/N. Com 200 candidatas, a chance é 1/200, ou 0,5%. Com 2 candidatas, 50%. O jogo inteiro consiste em reduzir N o mais rápido possível, e cada palpite é uma pergunta que parte a lista em grupos, um grupo para cada padrão de cores.

Informação: por que o logaritmo aparece

Imagine que a resposta é uma entre N opções igualmente prováveis. Uma pergunta de sim ou não bem feita corta a lista pela metade. Quantas perguntas desse tipo são necessárias? É o número $k$ tal que $2^k = N$ , ou seja, $k = \log_2 N$ . Essa quantidade se mede em bits.

I = \log_2 N

Bits necessários para identificar uma entre N opções igualmente prováveis.

Com 200 candidatas, $\log_2 200$ dá cerca de 7,64 bits. Um palpite no jogo não é uma pergunta de sim ou não: ele tem até 243 respostas, então pode render até $\log_2 243$ , cerca de 7,92 bits, na melhor das hipóteses. Nenhuma palavra real chega perto disso, mas a comparação mostra o limite teórico.

Bits = log₂ N: dobrar as candidatas acrescenta só 1 bit. Com 200 são cerca de 7,64 bits; com 243 padrões, cerca de 7,92.

Quando um palpite divide as N candidatas em grupos de tamanhos $n_1, n_2, \dots, n_k$ , a probabilidade de cair no grupo $i$ é $p_i = n_i/N$ . Duas medidas avaliam a qualidade do palpite:

E[\text{restantes}] = \sum_i p_i \cdot n_i = \frac{\sum_i n_i^2}{N}

Número esperado de candidatas que sobram depois do palpite.

H = \sum_i p_i \log_2 \frac{1}{p_i}

Entropia: informação esperada do palpite, em bits.

A primeira é intuitiva: você cai num grupo com probabilidade proporcional ao tamanho dele, e sobra exatamente esse tamanho. A segunda, a entropia de Shannon, mede em média quantas “metades” o palpite corta. Quanto menor a primeira e maior a segunda, melhor o palpite.

Exemplo resolvido: comparando dois palpites

Suponha 200 candidatas restantes (números hipotéticos). O palpite A divide a lista em quatro grupos de tamanhos 80, 60, 40 e 20. O palpite B divide em quatro grupos de 50. Qual é melhor?

Palpite A deixa grupos de 80, 60, 40 e 20 candidatas; o palpite B deixa quatro grupos iguais de 50.

Palpite A contra palpite B

$\displaystyle p = 0{,}4;\ 0{,}3;\ 0{,}2;\ 0{,}1$ Probabilidades do palpite A: cada grupo dividido por 200.
$\displaystyle \frac{80^2+60^2+40^2+20^2}{200} = \frac{12\,000}{200} = 60$ Candidatas esperadas no palpite A: some os quadrados e divida por 200.
$\displaystyle \frac{4 \cdot 50^2}{200} = \frac{10\,000}{200} = 50$ Candidatas esperadas no palpite B.
$\displaystyle 0{,}4\log_2 2{,}5 + 0{,}3\log_2 \tfrac{10}{3} + 0{,}2\log_2 5 + 0{,}1\log_2 10 \approx 1{,}85$ Entropia do palpite A, em bits (arredondada).
$\displaystyle 4 \cdot \tfrac14 \log_2 4 = 2$ Entropia do palpite B: quatro grupos iguais dão exatamente 2 bits.
Conclusão: B deixa menos candidatas em média e rende mais informação. Mesmo número de grupos, mas grupos equilibrados valem mais.

Verificação. Os grupos de A somam 80 + 60 + 40 + 20 = 200 e os de B somam 4 × 50 = 200, então nenhuma candidata sumiu. As probabilidades de A somam 0,4 + 0,3 + 0,2 + 0,1 = 1. Quatro grupos nunca rendem mais que $\log_2 4$ = 2 bits, e esse máximo só ocorre com grupos iguais, exatamente o caso B. Por fim, depois de B restam 50 candidatas; com $\log_2 50$ ≈ 5,64 bits ainda faltando, fica claro por que o jogo exige mais de uma tentativa.

Candidatas esperadas depois do palpite: 60 com A (grupos grandes pesam mais) contra 50 com B, que divide a lista por igual.

Erros comuns

Confundir sequências com palavras. 26 elevado a 5 conta sequências; a lista real de respostas é muito menor, e é ela que define N.
Usar arranjo quando há repetição. Palavras reais repetem letras; o arranjo simples de 7.893.600 só vale se as letras forem todas distintas.
Achar que mais verdes no primeiro palpite é sempre melhor. O que importa é o tamanho esperado do grupo onde você cai, não a cor bonita de uma rodada.
Calcular a média simples dos grupos. A média de 80, 60, 40 e 20 é 50, mas o esperado é 60, porque grupos grandes são mais prováveis. Cada grupo pesa pelo próprio tamanho.
Usar logaritmo na base errada. Bit é base 2. Com logaritmo natural a unidade vira “nat”; converta dividindo por $\ln 2$ .

Perguntas frequentes

Quantas palavras de cinco letras são possíveis com o alfabeto de 26 letras?

Como sequências, 26 elevado a 5, que dá 11.881.376. Sem repetir letras, 26 × 25 × 24 × 23 × 22 = 7.893.600. Palavras reais são uma fração pequena disso.

O que significa um palpite render 2 bits?

Que, em média, ele reduz as candidatas como duas perguntas de sim ou não bem feitas, isto é, a um quarto do tamanho original.

Por que o número esperado usa a soma dos quadrados?

Porque você cai no grupo i com probabilidade n_i/N e, nesse caso, sobram n_i candidatas. Somando n_i/N vezes n_i para todos os grupos, obtém-se a soma dos quadrados dividida por N.

Dá para garantir o acerto em poucas tentativas?

Não há garantia geral: depende da lista de palavras. O que a matemática oferece é um critério para escolher palpites que, em média, cortam mais a lista.