Matemática del juego de palabras: conteo, probabilidad y bits

Adivinar una palabra de cinco letras en seis intentos se volvió rutina diaria para mucha gente, y la pregunta “¿cuál es la mejor palabra para empezar?” aparece en cualquier sobremesa. Detrás hay matemática seria: conteo, probabilidad y teoría de la información. Aquí el juego es solo el punto de partida para aprender esas tres ideas, útiles mucho más allá de él. Las listas y los números de los ejemplos son hipotéticos, elegidos para que las cuentas salgan limpias.

Conteo: ¿cuántas palabras de cinco letras existen?

Empieza por el principio multiplicativo: si una elección tiene $a$ opciones y otra, independiente, tiene $b$ , el par tiene $a \cdot b$ posibilidades. Una secuencia de cinco letras, con 26 letras y repetición permitida, tiene 26 opciones en cada posición.

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

Secuencias de cinco letras con repetición (principio multiplicativo).

Si las cinco letras deben ser distintas, la primera posición tiene 26 opciones, la segunda 25, y así sucesivamente. Eso es una variación (permutación) de 26 elementos tomados de 5 en 5.

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

Secuencias de cinco letras sin repetir letra.

Casi ninguna de estas secuencias es una palabra real. La lista de respuestas de un juego así tiene del orden de unos miles de palabras, una fracción mínima de los 11,9 millones de secuencias. Por eso el juego es posible: el idioma ya descarta casi todo antes del primer intento.

Otro conteo útil: cada casilla de la respuesta del juego recibe uno de tres colores (letra correcta en su lugar, letra presente en otro lugar, letra ausente). Con cinco casillas hay $3^5$ = 243 patrones posibles. Algunos nunca ocurren, pero 243 es el tope de grupos que puede crear un solo intento.

Probabilidad: la chance de acertar al azar

Si quedan N candidatas igualmente probables, elegir una al azar acierta con probabilidad 1/N. Con 200 candidatas es 1/200, o 0,5%. Con 2 candidatas, 50%. Todo el juego consiste en reducir N lo más rápido posible, y cada intento es una pregunta que parte la lista en grupos, uno por cada patrón de colores.

Información: por qué aparece el logaritmo

Supón que la respuesta es una entre N opciones igualmente probables. Una buena pregunta de sí o no corta la lista a la mitad. ¿Cuántas preguntas así hacen falta? El número $k$ con $2^k = N$ , es decir, $k = \log_2 N$ . Esa cantidad se mide en bits.

I = \log_2 N

Bits necesarios para identificar una entre N opciones igualmente probables.

Con 200 candidatas, $\log_2 200$ es cerca de 7,64 bits. Un intento del juego no es una pregunta de sí o no: tiene hasta 243 respuestas, así que en el mejor caso aportaría $\log_2 243$ , cerca de 7,92 bits. Ninguna palabra real se acerca, pero la comparación muestra el límite teórico.

Bits = log₂ N: duplicar las candidatas suma solo 1 bit. Con 200 son cerca de 7,64 bits; con 243 patrones, cerca de 7,92.

Cuando un intento divide las N candidatas en grupos de tamaños $n_1, n_2, \dots, n_k$ , la probabilidad de caer en el grupo $i$ es $p_i = n_i/N$ . Dos medidas evalúan el intento:

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

Número esperado de candidatas que quedan tras el intento.

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

Entropía: información esperada del intento, en bits.

La primera es intuitiva: caes en un grupo con probabilidad proporcional a su tamaño, y te queda justo ese tamaño. La segunda, la entropía de Shannon, mide cuántas “mitades” corta el intento en promedio. Menos restantes esperadas y más entropía significan un mejor intento.

Ejemplo resuelto: comparar dos intentos

Supón que quedan 200 candidatas (números hipotéticos). El intento A las divide en cuatro grupos de 80, 60, 40 y 20. El intento B, en cuatro grupos de 50. ¿Cuál conviene?

El intento A deja grupos de 80, 60, 40 y 20 candidatas; el intento B deja cuatro grupos iguales de 50.

Intento A contra intento B

$\displaystyle p = 0{,}4;\ 0{,}3;\ 0{,}2;\ 0{,}1$ Probabilidades del intento A: cada grupo entre 200.
$\displaystyle \frac{80^2+60^2+40^2+20^2}{200} = \frac{12\,000}{200} = 60$ Candidatas esperadas tras A: suma los cuadrados y divide entre 200.
$\displaystyle \frac{4 \cdot 50^2}{200} = \frac{10\,000}{200} = 50$ Candidatas esperadas tras 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$ Entropía del intento A, en bits (redondeada).
$\displaystyle 4 \cdot \tfrac14 \log_2 4 = 2$ Entropía del intento B: cuatro grupos iguales dan exactamente 2 bits.
Conclusión: B deja menos candidatas en promedio y aporta más información. Mismo número de grupos, pero los grupos parejos valen más.

Verificación. Los grupos de A suman 80 + 60 + 40 + 20 = 200 y los de B, 4 × 50 = 200: no se perdió ninguna candidata. Las probabilidades de A suman 0,4 + 0,3 + 0,2 + 0,1 = 1. Cuatro grupos nunca dan más de $\log_2 4$ = 2 bits, y ese máximo solo ocurre con grupos iguales, justo el caso B. Tras B quedan 50 candidatas, unos 5,64 bits por resolver, y por eso el juego exige más de un intento.

Candidatas esperadas después del intento: 60 con A (los grupos grandes pesan más) frente a 50 con B, que divide la lista por igual.

Errores comunes

Confundir secuencias con palabras. 26 elevado a 5 cuenta secuencias; la lista real de respuestas es mucho menor y es la que define N.
Usar variaciones sin repetición cuando hay repetición. Las palabras reales repiten letras; los 7.893.600 solo valen con letras distintas.
Creer que más verdes en el primer intento siempre es mejor. Importa el tamaño esperado del grupo donde caes, no una ronda con suerte.
Sacar el promedio simple de los grupos. El promedio de 80, 60, 40 y 20 es 50, pero el esperado es 60, porque los grupos grandes son más probables.
Usar la base equivocada. Bit es base 2. Con logaritmo natural la unidad es el “nat”; convierte dividiendo entre $\ln 2$ .

Preguntas frecuentes

¿Cuántas combinaciones de cinco letras se pueden formar con 26 letras?

Como secuencias, 26 elevado a 5, que da 11.881.376. Sin repetir letras, 26 × 25 × 24 × 23 × 22 = 7.893.600. Las palabras reales son una fracción pequeña.

¿Qué significa que un intento aporte 2 bits?

Que en promedio reduce las candidatas como dos buenas preguntas de sí o no, es decir, a la cuarta parte.

¿Por qué el valor esperado usa la suma de cuadrados?

Caes en el grupo i con probabilidad n_i/N y te quedan n_i candidatas. Sumando n_i/N por n_i en todos los grupos se obtiene la suma de cuadrados entre N.

¿La matemática garantiza acertar en pocos intentos?

No en general; depende de la lista de palabras. Lo que ofrece es un criterio para elegir intentos que, en promedio, recortan más la lista.