¿Cuántos dígitos deberíamos inspeccionar en un número normal representado en base 28 (alfabeto español más el espacio) para que la probabilidad de...

Vamos a darle un vuelco "ingenieril" a esta pregunta, y, aunque no respondamos la pregunta tal como está planteada, me parece interesante explotar esta vena. Y de paso mostrarle a un niño que la frase "en un lugar de la mancha" aparece entre los dígitos de π. Vamos a suponer de ahora en adelante que el número normal es π.

La respuesta de David

N>−ln2ln(1–28−n)−1+n≈3,738⋅1034N>−ln⁡2ln⁡(1–28−n)−1+n≈3,738⋅1034

nos da el número de dígitos necesarios para tener una probabilidad > 1/2 de que la frase "en un lugar de la mancha" aparezca en la secuencia de dígitos de un número normal.

La fórmula supone que estamos representando los dígitos del número con las letras del alfabeto. Las palabras están representadas por sus propias letras.

Pero, ¿y si hiciéramos al revés? Podríamos representar las letras con un dígito. Da la tremenda casualidad que solo hay diez letras distintas en la frase, así que podríamos hacer la siguiente equivalencia:

a = 0

ch = 1

d = 2

e = 3

g = 4

l = 5

m = 6

n = 7

r = 8

u = 9

La frase "en un lugar de la mancha" se transformaría en:

en un lugar de la mancha

37 97 59408 23 50 60710

379759408235060710 (Pequeña trampa, eliminamos los espacios)

La frase tendría 18 caracteres.

Si aplicamos la fórmula de David, tendríamos 10 dígitos para la base y 18 dígitos para la secuencia que queremos buscar:

N>−ln2ln(1–10−18)−1+18≈∞N>−ln⁡2ln⁡(1–10−18)−1+18≈∞

Mi calculadora se desborda.

Hagamos lo siguiente, partamos la frase por la mitad, la secuencia sería de 9 dígitos:

N>−ln2ln(1–10−9)−1+9≈693147207N>−ln⁡2ln⁡(1–10−9)−1+9≈693147207

Casi 700 mil dígitos. Perfecto, porque existe un sitio web que te permite buscar secuencias de dígitos en 2000 millones de cifras de π.

Irrational Numbers Search Engine

Las frases serían "en un lugar" y "de la mancha", que corresponden con los dígitos

379759408 y 235060710

Esta es la respuesta del sitio web. Cambiamos los dígitos por sus letras equivalentes.

The numeric string 379759408 appears at the 85,132,582nd decimal digit of Pi.

lgmlneddechgchrrmchggmrenunlugardmgrlagmchggrnadanllu

^ <-- 85,132,582nd digit

The numeric string 235060710 appears at the 1,902,759,546th decimal digit of Pi.

mudglchumchglumnlugduadelamanchadgdchnrurdchdllrlmgnal

^ <-- 1,902,759,546th digit

(Como no es posible especificar una fuente monoespaciada en Quora, no aparecen alineadas las flechitas de posición del texto encontrado)

Bueno, "en un lugar" y "de la mancha" se pueden encontrar en las cifras de π.

En un lugar de la Mancha es la frase con la que empieza la narración de El ingenioso hidalgo Don Quijote de la Mancha. Esta maravillosa novela tiene 381226 palabras (yo las conté, y en 1972 escribí un programa en FORTRAN para dibujar un histograma de frecuencia de las letras de la primera página, la letra más frecuente era la "S"), sin contar repeticiones son 22942 palabras. Las palabras más frecuentes, apartando artículos, preposiciones y similares son don, Quijote y Sancho. Hay 11175 palabras que solamente aparecen una vez, aunque puede ser un verbo repetido que solo se conjugó en un tiempo distinto cada vez). El archivo tiene cerca de 2044000 caracteres.

Cada palabra del Quijote que aparece en la lista de 22942 palabras se puede representar por su posición en la lista. Con solo 2 bytes podemos almacenar ese número (2 bytes pueden contar hasta 256 x 256 = 65536)

Es decir, las 381226 palabras se pueden sustituir por su posición en la lista, la obra estaría completa, pero se reduciría su tamaño de 2044000 caracteres a solo 318226 x 2 = 636452 caracteres.

Este método de sustituir pedazos de un archivo por una entrada de diccionario es un método que se usa para comprimir archivos, llamado codificación por diccionario. Codificación por diccionario - Wikipedia, la enciclopedia libre

Ajá, ¿y si usamos un diccionario para representar nuestra frase "en un lugar de la mancha"?

Podemos definir este diccionario:

0 = de

1 = en

2 = la

3 = lugar

4 = mancha

5 = un

6 = t

7 = x

8 = y

9 = z

en un lugar de la mancha se convierte en:

153024

Y la posición en el desarrollo de π es:

0439545058220926547815302419243428754966152987

^ <-- 1,036,177th digit

En realidad, haciendo las sustituciones debería ser

04395450582209... latunmanchaxyenunlugardelamanchaenzlamanchalugarmanchala... 8754966152987

Nuestro diccionario todavía tiene espacio para más palabras. ¿Qué tal con estas:?

0 = de

1 = en

2 = la

3 = lugar

4 = mancha

5 = un

6 = cuyo

7 = nombre

8 = no

9 = quiero

Podríamos tener la frase:

en un lugar de la mancha de cuyo nombre no quiero que se representa con

15302406789

Sin embargo el sitio web no encuentra la frase dentro de los dos mil millones de cifras de π.

Solo aparece la frase en un lugar de la mancha de cuyo nombre

que se codifica con

153024067

Y aparece aquí:

7310559266412642985615302406708405483257383094476

^ <-- 781,197,393rd digit

Pues sí, "en un lugar de la mancha" aparece en el desarrollo de π

Obviamente esto no se puede extender mucho, porque crece de manera exponencial.

A menos que hagamos como el extraterrrestre que se llevó una enciclopedia codificada como una simple marca en una regla :-). (Véase Martin Gardner, ¡Ajá! Paradojas que te hacen pensar)

Aquí arañamos un poquito el tema de compresión de datos, un área muy importante de las ciencias de la computación.