Sacar la bola "n" en la extracción número "n" (soluciones y sorpresa matemática)

En una entrada anterior se planteaba el siguiente problema:

Tenemos una urna con 5 bolas numeradas del 1 al 5. Hay que sacarlas de una en una al azar, sin mirar. Se pierde el juego si sacamos la bola "n" en la extracción número "n".

Abordar dicho problema con un enfoque de probabilidad clásica realizando el diagrama de árbol es factible pero muy tedioso, teniendo en cuenta que con 5 bolas el árbol completo tiene 5! = 120 ramas. En realidad, dicho proceso no dista mucho de calcular todas las permutaciones y comprobar cuáles cumplen las condiciones (método exhaustivo).

Si aumentamos el número de bolas en la urna olvidémonos del método exhaustivo manual. Podemos utilizar programación para que realice dicho método exhaustivo. El problema es el tiempo de computación. Para hacernos una idea, con 13 bolas en la urna tenemos 6.227.020.800 permutaciones diferentes que crear y comprobar si cumplen o no la condición del enunciado (aproximadamente 52 minutos con mi ordenador).

Muchos problemas no tienen mucho interés desde el punto de vista algorítmico-teórico porque es fácil definir el algoritmo que resuelve el problema, pero llevado a la práctica con los ordenadores de los que disponemos actualmente el tiempo de computación de dicho algoritmo puede hacer inviable su resolución en un tiempo "razonable". Y esto obliga a tener que optimizar los algoritmos o buscar alternativas a los mismos.

Volviendo al problema, he creado un programa en Python que resuelve la generalización del problema con N bolas. Como se planteaba al final de la entrada anterior.

He utilizado dos métodos. Empiezo por el segundo, método exhaustivo. Se calculan todas las permutaciones con la librería itertools de Python y se recorren comprobando si cumplen o no la condición de que ninguna bola salga en la posición que indica su número. Para N pequeño (<10) el tiempo de ejecución es razonable, no así conforme se aumenta el número de bolas.

El primer método utilizado es matemáticamente mucho más interesante. Hace uso del concepto de desarreglo, que expliqué en la entrada anterior.

No es difícil ver la relación de los desarreglos con el problema planteado de las bolas numeradas. Que ninguna bola salga en el orden que indica su número equivale a decir que en la permutación del conjunto {1, 2, 3, 4, 5} ningún elemento coincida con su posición original. Por tanto, si calculamos el número de desarreglos del conjunto {1, 2, ..., N} la probabilidad de ganar el juego será: número de desarreglos / permutaciones totales. Es decir, el subfactorial dividido entre el factorial.

p(ganar juego con N bolas) = !N / N! 

Una fórmula muy bonita y computacionalmente mucho más rápida que el método exhaustivo.

Nota: Para calcular el factorial y el subfactorial en Python he utilizado la librería SymPy.

 

En el caso del problema original, N = 5, la probabilidad de ganar es aproximadamente 0.36666666666666664. Por lo que tenemos la probabilidad cuantificada y podemos decir que es más fácil perder el juego que ganarlo.

Además se planteaba la pregunta de si nos parecía lucrativo que nos doblaran la apuesta en caso de ganar, teniendo en cuenta el riesgo que se asume. La respuesta es negativa, dado que a la larga ganaremos aproximadamente un 36'67% de las veces que juguemos y si sólo nos doblan la apuesta lo más probable es acabar perdiendo dinero en dicho juego.

Por último, se planteaba la siguiente pregunta:

Conforme aumentamos el número de bolas, ganar el juego ¿es más fácil, más difícil o va variando?

He creado otro programa en Python que devuelve las probabilidades de ganar el juego variando el número de bolas. El resultado obtenido se recoge en la siguiente tabla: 

N	Probabilidad de ganar
2	0.5
3	0.3333333333333333
4	0.375
5	0.36666666666666664
6	0.3680555555555556
7	0.3678571428571429
8	0.36788194444444444
9	0.36787918871252206
10	0.3678794642857143
11	0.3678794392336059
12	0.3678794413212816
13	0.36787944116069116
14	0.3678794411721619
15	0.3678794411713972
16	0.367879441171445
17	0.36787944117144217
18	0.36787944117144233
19	0.36787944117144233
20	0.36787944117144233
21	0.36787944117144233
22	0.36787944117144233
23	0.36787944117144233
24	0.36787944117144233
25	0.36787944117144233
26	0.36787944117144233
27	0.36787944117144233
28	0.36787944117144233
29	0.36787944117144233
30	0.36787944117144233

Vemos que en las primeras N la probabilidad una veces sube y otras baja pero que conforme aumenta N la probabilidad se va estabilizando en torno a un valor: 0.36787944117144233. Podríamos decir que a nivel práctico a partir de 5 bolas la probabilidad de ganar el juego no cambia demasiado.

Y aquí podría acabar esta entrada. Pero las matemáticas están repletas de conexiones sorprendentes y en ocasiones inesperadas. ¿Alguien al leer el problema de las bolas numeradas pensó en el famoso número e?

Pues aquí va su aparición estelar: ese número al cual tiende la probabilidad conforme aumentamos el número de bolas, 0.3678794411714423..., es exactamente el inverso del número e.

1/e =  0.3678794411714423...

Dejo como ejercicio a quien quiera la explicación de este hecho (pista: mirar en la entrada anterior la fórmula del subfactorial).

Subfactorial y desarreglos

 

En Combinatoria, se llama permutaciones al número de formas de ordenar una cantidad de elementos usándolos todos y sin que se repita ninguno.

Por ejemplo, si tenemos 3 elementos (a, b y c) las diferentes formas de ordenarlos con esas condiciones son:

a b c

a c b

b a c

b c a

c a b

c b a 

Un total de 6 posibilidades. En lugar de tener que escribir todas las posibilidades y contar la combinatoria nos permite hacer el cálculo utilizando la famosa función factorial (n!).

3! = 3 · 2 · 1 = 6

 

Hay un subconjunto de las permutaciones que llamamos desarreglos, que son aquellas ordenaciones en las que ningún elemento está en su posición original.

Siguiendo con el mismo conjunto anterior {a, b, c} sus desarreglos son:

b c a

c a b

Un total de 2 posibilidades (en cualquier otro orden como mínimo un elemento está en su posición original).

Para calcular la cantidad de desarreglos de un conjunto podemos utilizar la no tan famosa función subfactorial (!n).

Su fórmula viene dada por la siguiente expresión: 

 

En nuestro ejemplo: 

!3 = 3! · (1/2! - 1/3!) = 6 · (1/2 - 1/6) = 6/2 - 6/6 = 3 - 1 = 2 

 

¿Conocías la función subfactorial y los desarreglos? ¿Tienen alguna relación con la entrada anterior? 

 

El factorial de las mil y una noches.

Leyendo en Internet algunas cosas relacionadas con lo que se trata en la entrada anterior llegué a una de las "delicias digitales endiabladamente difíciles" (en palabras del autor). Se trata de una cuestión incluida en el capítulo 37 del libro La maravilla de los números, de Clifford A. Pickover. Así que desempolvo el libro, que lo tengo en mi estantería.

Incluyo aquí el fragmento al que me refiero:

"Desde la edad de trece años, cada 1001 días el doctor Googol lee Las mil y una noches, lo que significa que lee esa obra una vez cada 2,74 años. Con la excepción del Corán, ninguna otra obra literaria árabe se conoce mejor ni tiene más influencia en Occidente que Las mil y una noches. Esta colección de relatos está agrupada en derredor de uno central relativo a un sultán y a sus amantes. Después de descubrir que su esposa le había sido infiel, el sultán hace la promesa de tomar una nueva novia cada día y hacerla ejecutar al día siguiente.

Cuando Sahrazad fue elegida como su nueva esposa, cada atardecer ella le contaba un cuento al sultán, pero no lo terminaba, prometiendo hacerlo a la siguiente noche si sobrevivía. Esto continuó durante mil y una noches, hasta que el sultán quedó profundamente enamorado de Sahrazad y olvidó sus crueles planes de ejecución.

Una noche, después de haber leído Las mil y una noches, el doctor Googol empezó a preguntarse acerca de un número especial llamado el factorial de las mil y una noches. Este número está definido con el valor de x tal que x! tiene 1001 dígitos. Los factoriales crecen bastante rápidamente: 5!=120, 10!=3.682.800 y 15!=1.307.674.368.000. ¿Cuál es el factorial de las mil y una noches?"

Aprovechando lo que expliqué en la entrada anterior, lo que estamos buscando es el menor número x tal que x! tenga 1001 cifras, entonces, utilizando la expresión cifras de x! = [log(x!)] + 1 obtenemos:

1001 = [log(x!)]+1 que es equivalente a [log(x!)]=1000.

Como log(x!)=log(1)+log(2)+...+log(x) lo que podemos hacer es ir sumando los logaritmos decimales de los números naturales hasta que la parte entera del resultado sea 1000 (teniendo en cuenta que podríamos pasarnos de largo). O equivalentemente, hasta sumar el logaritmo decimal del número que haga que el resultado sea (por primera vez) mayor que 1000.

Con pequeñas modificaciones al programa de la entrada anterior construimos el siguiente código:

#include < stdlib.h >
#include < iostream >
#include < math.h >
main()
{
    double r=0;
    unsigned long int i=2, numero=1001;
    while(r < numero-1)
    {
        r+=log10(i);
        i++;
    }
    i--;  // quitamos el último incremento
    std::cout < < "El primer factorial cuyo resultado tiene por lo menos " < < numero < < " cifras es " < < i < < "!." < < std::endl;
    return 0;
}

La ejecución del programa anterior devuelve:

El primer factorial cuyo resultado tiene por lo menos 1001 cifras es 450!.

Podría ser que 450! tuviera más de 1001 cifras, dado que la condición que imponemos es que por lo menos tenga esa cantidad de cifras. Si ejecutamos el programa de la entrada anterior obtenemos:

El factorial de 450 tiene 1001 cifras.

O si alguien no se fía de mis dotes de programador, también puede preguntárselo a Wolfram Alpha :-)

Problema resuelto. Bueno, este en particular y el general de hallar el menor número x cuyo factorial tenga por lo menos n cifras (siempre que el tamaño de n no desborde la variable).

Curiosidad: Al igual que en la obra El prodigio de los números, Pickover dedica el libro al cuadrado mágico apocalíptico.

Clifford A. Pickover

¿Cuántas cifras tiene un número? Por ejemplo, el factorial de 1.000.000

El sistema de numeración que utilizamos es posicional y decimal, es decir que utilizando 10 dígitos (0, 1, 2, 3, 4, 5, 6, 7, 8 y 9) podemos escribir cualquier número entero.

¿Cuántas cifras tiene el número 92.368.556? Una pregunta bastante sencilla. Contamos y listo. 8 cifras.

¿Cuántas cifras tiene el factorial de 1.001? Pues ahora la cosa no es tan sencilla. Calcular el factorial de 1.001 y contar sus cifras es una posibilidad, pero en vista de que el número es bastante elevado vamos a intentar encontrar una alternativa que nos evite calcular el factorial.

Si volvemos al hecho de que usamos un sistema decimal, podemos concluir fácilmente que se añade una cifra más cada vez que damos un salto a la siguiente potencia de 10.

En 10¹ = 10 comienzan los números de 2 cifras.

En 10² = 100 comienzan los números de 3 cifras.

En 10³ = 1.000 comienzan los números de 4 cifras

... si generalizamos esta propiedad, podemos formularla como ...

En 10^n comienzan los números de n+1 cifras.

Si el cambio de cifras se produce en las potencias de 10, para conocer cuántas cifras tiene un número podemos utilizar la operación inversa a la exponenciación de base 10: los logaritmos decimales.

Por ejemplo, si tenemos en cuenta que log(10)=1 y log(100)=2, al calcular el logaritmo decimal de cualquier número entre 10 y 100 obtenemos, dado que el logaritmo es una función estrictamente creciente, un resultado decimal entre 1 y 2.

Entonces, la cantidad de cifras de un número cualquiera se obtiene sumando 1 a la parte entera de su logaritmo decimal.

Ejemplo: ¿Cuántas cifras tiene el número 92.368.556?

log(92368556) = 7,96552415434

La parte entera, a partir de ahora denotada por [], es [7,96552415434]=7.

Por tanto, el número 92.368.556 tiene 8 (7+1) cifras.

Si aplicamos esto mismo a la pregunta de cuántas cifras tiene 1001!, tendríamos:

cantidad de cifras de 1001! = [log(1001!)]+1

1001! es un número elevado para las calculadoras, pero wxMaxima puede calcular la expresión [log(1001!)]+1 directamente con el siguiente comando, sin que se produzca ningún desbordamiento:

entier(log(1001!)/log(10))+1;

Téngase en cuenta que en wxMaxima la función log corresponde al logaritmo neperiano y no al decimal, por eso aparece en la expresión la división entre log(10). El resultado que devuelve wxMaxima es:

2571

Bien, ya sabemos cuántas cifras tiene el factorial de 1001, pero además de que hemos hecho la gran trampa de que wxMaxima sí ha calculado el factorial de 1001, ¿qué pasa si el número es mayor? Pongamos por ejemplo que queremos saber cuántas cifras tiene 1.000.000!

Aquí wxMaxima ya no arroja resultados. Podríamos recurrir a la programación para definir una función que calcule el factorial multiplicando tipos enteros, pero la mayoría de lenguajes de programación tiene un rango limitado para sus tipos de variables. Por ejemplo, un tipo unsigned long long en el lenguaje de programación C tiene un rango de 0 a 18.446.744.073.709.551.615. Cualquier operación cuyo resultado sea mayor provoca un desbordamiento. Otros lenguajes de programación, como python, ya llevan implementadas en sus librerías funciones que efectúan las operaciones de este tipo sin provocar desbordamiento.

 

En cualquier caso, lo que estamos pensando es si puedo evitar el cálculo del factorial porque lo único que me interesa es saber cuántas cifras tiene. Así que volvemos a utilizar la expresión general:

cifras de n! = [log(n!)]+1

Nuestro problema era que no queremos/podemos calcular el factorial y si observamos la propiedad anterior resulta que ahora no sólo tengo que calcular un factorial sino que además tengo que calcular un logaritmo. Menudo invento. Bueno, tranquilidad. El factorial son productos y sabemos que los logaritmos tienen la propiedad de "transformar las multiplicaciones en sumas": log(a·b)=log(a)+log(b).

Así pues,

log(1000000!) = log(1000000·999999·...·2·1)=log(1000000)+log(999999)+...+log(2)+log(1).

¿Qué ganamos con esto? Pues reducir considerablemente el orden de los números con los que se trabaja. Los números decimales que aparecen en los sumandos de log(1000000)+...+log(2)+log(1) están comprendidos entre 0 y 6 (incluidos). La precisión de los tipos decimales de cualquier lenguaje de programación es más que suficiente para el cálculo anterior, especialmente si tenemos en cuenta que lo que nos interesa ahora es la parte entera del resultado del sumatorio.

Por ejemplo, en C++ podemos escribir el siguiente programa:

#include < stdlib.h >
#include < iostream >
#include < math.h >
main()
{
    double r=0;
    unsigned long int numero=1000000;
    for(unsigned long int n=1; n<=numero; n++)
    {
        r+=log10(n);
    } //for n
    unsigned long int cifras_factorial= (unsigned long int) r;
    cifras_factorial++;
    std::cout < < "El factorial de " < < numero < < " tiene " < < cifras_factorial < < " cifras." < < std::endl;
    return 0;
}

La ejecución del programa anterior devuelve la siguiente sentencia:

El factorial de 1000000 tiene 5565709 cifras.

Como curiosidad final, hice un programa en python que calcula todas las cifras del factorial de 1000000.


Entrada relacionada:
- El factorial de las mil y una noches.