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? 

 

Matemática recreativa: capicúa de 6 cifras impares y divisible entre todas sus cifras

Vamos a por otro problema (n. 97) del libro "Ludopatía Matemática" de Mariano Mataix. Tiene el siguiente enunciado:

Veamos, una vez más, cómo está su teoría de números. Han de determinarse dos números, cada uno de 6 cifras impares. Ambos son capicúas y cumplen la condición de que ninguna cifra se repite más de dos veces. Además, cada número es divisible por cada una de sus cifras.

Imagen creada con IA

 

Como en entradas anteriores (1, 2, 3, 4, 5, 6) donde abordé otros problemas del libro, he construido un algoritmo en Python para resolver el problema. El nivel del problema es fácil para resolver, utilizando la función permutations del módulo itertools.

Ver código en repositorio de GitHub.

Problema de los cartones de bingo especiales: una solución con Python

 En la entrada anterior puse un problema en el que teníamos que contar cuántos cartones de bingo diferentes podíamos construir siguiendo unas reglas dadas: sin que se repita ninguna fila, columna o diagonal.

 Que ninguna pareja de cartones tenga alguna fila igual se entiende perfectamente. Lo mismo con columnas. Pero, ¿qué se entiende por diagonal del cartón? Si vemos el cartón como una matriz de 5x5, ¿hablamos sólo de la diagonal principal de la matriz? ¿también la diagonal secundaria (antidiagonal)? En este sentido el enunciado me genera dudas de interpretación. Así que desarrollaré un programa que pueda contestar a la pregunta interpretando ambas opciones.

El código en Python puede encontrarse en el repositorio de Matemática Recreativa que creé en GitHub.

Si queremos quitar la condición de la antidiagonal podemos comentar las líneas:

    if antidiagonal in antidiagonales:
        continue

 De hecho, el resultado no varía. Pero es que tampoco lo hace si quitamos la condición de las diagonales. Y aún más "sorprendente" es que tampoco varía si quitamos la condición de que no pueda haber dos matrices con alguna fila común.

Imagen extraída de https://www.youtube.com/watch?v=aumxFs2DO5o

 Pero eso no lo explica el algoritmo, sino que lo hacen las Matemáticas. La columna con menos combinaciones es la tercera, dado que hay una casilla negra a la que no hay que asignarle un número. Como en dicha columna podemos poner números en orden ascendente desde el 31 al 45 incluidos y sin poder repetirlos, tenemos el número combinatorio 15C4 que da 1365. Por tanto, tenemos una cota superior del número de soluciones al problema dado que podríamos tener cartones/matrices dentro de esas combinaciones con filas, diagonales o antidiagonales en común.

 Lo que pasa es que la solución al problema es exactamente 1365. ¿Por qué la restricción de la tercera columna es la más restrictiva sobre las condiciones de filas, diagonal y antidiagonal? Es decir, ¿por qué podemos asegurar que para cada una de las 1365 combinaciones para la tercera columna podemos rellenar un cartón completo que no comparta alguna fila, diagonal ni antidiagonal con el resto de cartones?

 La justificación no me parece tan fácil como podría pensarse en un principio. ¿Cuál es tu justificación?

¿Cuánto pesa la seguridad WiFi de mi router? (1ª parte)

La característica principal de las redes Wireless (comunicación inalámbrica) es que la información no se transmite a través de un cable, sino que la información "viaja" por el aire en forma de ondas electromagnéticas.

De esta manera podemos mover los dispositivos con cierta libertad (dentro del radio de acción del router), pero presenta el inconveniente de que cualquier persona que esté en la zona puede interceptar la información que se transmite por el aire.

Software que captura información de redes WiFi

Por ello se hace especialmente necesario en este tipo de conexiones cifrar los datos que se envían, de modo que la información interceptada no pueda leerse si no se posee la contraseña del cifrado. Los protocolos de cifrado de conexiones WiFi más extendidos son WEP y WPA/WPA2.

El cifrado WEP utiliza una clave, cuyo tamaño puede ser de 64 bits, de 128 bits o incluso 256 bits. La clave más habitual es la de 128 bits, que está formada por un vector de 24 bits y la contraseña de 104 bits.

¿Cuántos caracteres tiene una contraseña WEP-128? Un carácter hexadecimal (0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f) ocupa 4 bits (2^4=16), por tanto la contraseña WEP-128 puede contener hasta 26 (104:4) caracteres hexadecimales.

Ejemplo de contraseña WEP-128 de 26 caracteres hexadecimales: 03662a2352f235235bc146af49

A alguien se le puede ocurrir intentar romper la seguridad de la clave anterior "a lo bruto", es decir, probando claves hasta dar con la buena. En ese caso resultaría útil conocer cuántas claves se pueden formar con exactamente 26 caracteres hexadecimales. Podemos enfocar la cuestión anterior como si tuviéramos que llenar 26 espacios con 16 caracteres disponibles que se pueden repetir. Estamos por tanto ante un caso de variaciones con repetición:

16^26 = 20.282.409.603.651.670.423.947.251.286.016 combinaciones posibles.

Con el dato anterior resulta evidente que la probabilidad de acertar la clave probando algunas al azar es pequeñísima. Pero, ¿por qué no creamos un fichero (diccionario) con todas las combinaciones posibles y que un programa las vaya probando una a una? Hay dos cuestiones importantes respecto a la pregunta anterior: una es cuánto tiempo necesitamos para probar todas esas claves y otra, la que tratamos aquí, es el tamaño aproximado del diccionario.

¿Cuánta memoria del disco duro ocuparía el diccionario de todas las contraseñas posibles (de 26 caracteres)?

Cada combinación tiene 26 caracteres y cada carácter hexadecimal ocupa medio byte (4 bits) de memoria, lo que hace un total de (sin tener en cuenta el bit/byte que separa una combinación de la siguiente, en caso de que fuera necesario):

(26·16^26)/2 = 263.671.324.847.471.715.511.314.266.718.208 bytes

Es decir, mucho mucho muchísimo más que la capacidad de cualquier disco duro que podamos comprar. Por tanto, la estrategia de realizar un ataque por fuerza bruta con un diccionario de esas características no parece una buena idea.

Hasta aquí, desde un punto de vista teórico, se podría concluir que la combinatoria nos dice que la seguridad WiFi "pesa" demasiado y, por tanto, que podemos estar relativamente tranquilos. Pero en la práctica, la realidad es otra. Existe una serie de aspectos que deben tenerse en cuenta porque pueden hacer que nuestra seguridad WiFi caiga y se pueda romper fácilmente.

Continúa leyendo la segunda parte.