Algoritmo de Babai con Python

 En la entrada anterior expliqué y ejemplifiqué el Algoritmo de Babai para encontrar el vértice del n-paralelepípedo más cercano a un punto.

Podemos realizar un script en Python para dicho algoritmo. Utilizando la librería NumPy queda muy sencillo:

 

import numpy as np

def babai(B, w):
    # Calculamos los coeficientes del vector w en la base B
    v = np.linalg.solve(B, w)
    # Devolvemos el producto matricial de B por las coordenadas de v redondeadas
    return B @ np.round(v).astype(int) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

PD: Podéis encontrar en uno de mis repositorios de Github un script para probar el Algoritmo de Babai y la razón de Hadamard. 

Razón de ortogonalidad de Hadamard con Python

 En una entrada anterior hablé sobre la razón de ortogonalidad de Hadamard:

$$H(B) = \sqrt[n]{\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|}} $$

Podemos realizar un script en Python para calcular dicha razón, utilizando la librería NumPy:

import numpy as np

def razon_hadamard(B):
    # Calculamos el valor absoluto del determinante de la matriz
    det = np.abs(np.linalg.det(B))
    # Si el determinante es 0 la matriz no es una base y la función devuelve 0
    if not det:
        return 0
    n = len(B)
    # Definimos una variable prod_norm que calcula el producto de la norma de cada vector (columna)
    prod_norm = np.prod(np.linalg.norm(B, axis=0))
    # Devolvemos la razón
    return (det / prod_norm) ** (1/n) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

Matrices cuadradas aleatorias con determinante 1 o -1

Objetivo: generar una matriz cuadrada de números enteros aleatorios cuyo determinante sea 1 o -1.

Una primera idea puede ser realizar un bucle en el que generamos una matriz cuadrada de números enteros aleatorios hasta que se satisfaga la condición de que su determinante sea 1 o -1. El problema estaría resuelto, pero el algoritmo no es muy eficiente.

Voy a proponer a continuación otra solución. 

Problema previo: generar una matriz triangular de números enteros aleatorios cuyo determinante sea 1 o -1.

Este problema es muy sencillo teniendo en cuenta que el determinante de una matriz triangular es igual al producto de los elementos de su diagonal.

Únicamente necesitamos rellenar la diagonal con elementos del conjunto {-1, 1}, ceros por encima (o por debajo) de la diagonal y números enteros aleatorios en el resto de elementos de la matriz. 

Ejemplo de función en Python que calcula una matriz triangular de enteros aleatorios (entre -10 y 10, ambos incluidos) utilizando la librería NumPy.

import numpy as np
# Función para crear una matriz triangular de enteros con determinante 1 o -1
# n es la dimensión de la matriz
def matriz_det1(n):
    # Se crea una matriz M_azar con todos sus elementos aleatorios
    M_azar = np.random.randint(-10, 11, size=(n, n))
    # Se elige al azar si se construye una matriz triangular superior o inferior
    if np.random.randint(2):
        # Triangular superior: se cogen los elementos de M_azar por encima de la diagonal
        # con el resto de elementos iguales a 0 y se le suma una matriz diagonal con elementos 1 y -1
        MU = np.triu(M_azar, k=1) + np.diag(np.random.choice([-1, 1], size=n))
    else:
        # Triangular inferior: se cogen los elementos de M_azar por debajo de la diagonal
        # con el resto de elementos iguales a 0 y se le suma una matriz diagonal con elementos 1 y -1
        MU = np.tril(M_azar, k=-1)+ np.diag(np.random.choice([-1, 1], size=n))
    return MU 

Ejemplo de matriz (10x10) creada con dicho algoritmo:

 

Teniendo resuelto el problema previo, ahora podemos abordar el problema original. Las matrices resultantes del algoritmo anterior tienen el "inconveniente" de no ser lo suficientemente aleatorias, dado que son triangulares y tienen demasiados elementos 0 no aleatorios.

Sin embargo, sabemos que: 

- El determinante del producto de matrices es igual al producto de los determinates (|A·B|=|A|·|B|). Por tanto, si multiplicamos matrices cuyo determinante es 1 o -1 el resultado será una matriz cuyo determinante es 1 o -1.

- El producto de matrices triangulares no tiene porqué ser una matriz triangular.

Utilizando esto, podemos idear un algoritmo para el objetivo principal que consista en crear varias matrices triangulares resultantes del algoritmo anterior y multiplicarlas:

# Función para crear una matriz con determinante 1 o -1
# mediante la multiplicación de matrices triangulares
# n es la dimensión de la matriz y m el número de iteraciones
def genU(n, m):
    # Comenzamos con la matriz identidad
    U = np.eye(n, dtype=int)
    # Creamos "m" matrices triangulares con determinante 1 o -1 y las multiplicamos
    for k in range(m):
        U = U @ matriz_det1(n)
    return U

 Ejemplo de matriz creada con dicho algoritmo (n=5, m=10):

 

 

 

Advent of Code 2025

Cada diciembre, desde 2015, sale una nueva edición de Advent of Code. Es una web en la que proponen diariamente unos retos de programación, como si fuera un calendario de adviento.

 

 Este año la novedad es que sólo habrá 12 retos, en lugar de los 25 que había en las ediciones anteriores. Una de las características de dichos retos es que plantean problemas que puedes resolver utilizando cualquier lenguaje. Cada usuario tiene un conjunto de datos que debe tratar para dar solución a la pregunta planteada.

La falta de tiempo para dedicarle hizo que el año pasado me quedara en el día 15 de los 25 propuestos. Este año como son menos a ver si consigo acabarlos todos.

Iré subiendo en este repositorio de GitHub mis propuestas de resolución utilizando Python. Y cuando aparezca algo que me parezca interesante haré una entrada aparte en el blog para comentarlo.

El código del día 1 ya está subido :-) 

Probabilidad con baraja española: manotazo. Solución 3/3 (Matemáticas al rescate)

Todo comienza en un viaje familiar que inicia las vacaciones de verano. Un rato muerto. Una baraja española. Un recuerdo de juego en mi infancia. Y tras ir volteando cartas y diciendo los números consecutivos y "perder" casi todas las veces surge la pregunta: ¿qué probabilidad hay de ganar a este juego?

 Y ya tenemos la chispa encendida. Y siguen un papel y un boli con la probabilidad clásica, combinatoria, árboles y simplificaciones del problema para entender la magnitud real del mismo. Y la magnitud es demasiado grande para mis papeles. ¿Y si cojo el ordenador y programo un poco para contestar a la pregunta? Pero ahí también surgen dificultades.

Pero, como sucede con cierta frecuencia, en el proceso de investigar y buscar estrategias aparecen nuevos conocimientos que acaban hilándose hasta llegar al culmen.

Así que decidí dedicar algunos ratos libres para programar e ir contando en este blog todo de manera gradual y por fascículos.

Y antes de introducir el problema "grande" escribí esta entrada con un problema de urnas y bolas; y en esta otra entrada la solución (con la inesperada visita del número e). Intercalé esta entrada sobre el subfactorial y los desarreglos, que "casualidades de la vida" se utilizaban en la solución.

Parecía el fin de la cuestión y como quien cambia de tema aparece esta entrada sobre los polinomios de Laguerre y cómo calcularlos con Python y wxMaxima.

Y ahora sí, llega el problema original con la baraja de cartas. Enunciado en esta entrada, y primera solución es esta otra entrada. Pero nos encontramos con un problema de tiempos razonables de ejecución así que en esta nueva entrada cuento cómo hacer una aproximación empírica a la solución del problema.

Pero queda la traca final que pone fin a esta serie de entradas, como ya se ha puesto fin a la vacaciones de verano.

Resulta que existe una fórmula para calcular una generalización de los desarreglos cuando tenemos elementos que se repiten.

Teniendo r elementos diferentes, el primero que se repite n1 veces, el segundo n2 veces y así sucesivamente, el número de desarreglos viene dado por: 

Donde Pn_i es el polinomio de Laguerre de grado n_i. (Fuente) 

Por ejemplo, en una situación con 3 elementos que se repiten 1, 5 y 7 veces respectivamente, dentro de la integral definida tendremos (además de la exponencial de -x) los polinomios de Laguerre de grado 1, de grado 5 y de grado 7.

Por tanto, en nuestro problema original (13 números repetidos 4 veces), dentro de la integral tendremos 13 veces el polinomio de Laguerre de grado 4 (y la exponencial). Así que resolviendo esa integral podemos obtener la solución del problema.

En wxMaxima es muy sencillo y rápido (código en github):

Y la implementación en Python puede encontrarse también en mi repositorio de Matemática Recreativa de Github (ver código).

Con un tiempo de ejecución muy pequeño tenemos la respuesta al problema: la probabilidad de ganar en las condiciones planteadas es de aproximadamente 1,62%.

Recordad que con la estrategia de simulación empírica obtuvimos aproximadamente 1,63%. En este caso no necesitamos simulaciones, porque las Matemáticas tienen una manera relativamente sencilla de calcularlo, pero cabe destacar que la aproximación realizada es bastante buena.

¿Quién me iba a decir en casa de mi familiar cuando estaba jugando con la baraja española que acabaría utilizando integrales definidas con polinomios de Laguerre para contestar a mi pregunta sobre la probabilidad de ganar en el juego?

Pero una cosa sí que tengo constatada, cuando se dispone de tiempo libre siempre surgen buenas ideas. La rutina diaria y el ritmo de vida acelerado nos bloquean la creatividad. 

 

Probabilidad con baraja española: manotazo. Solución 2/3 (simulaciones)

 

En una entrada anterior planteé una cuestión de probabilidad en un juego de cartas con la baraja española.

Se resolvió el problema en esta entrada utilizando una estrategia exhaustiva: crear todas las permutaciones posibles y comprobar en cada una de ellas si se gana o se pierde el juego.

El problema de dicha resolución es el tiempo de ejecución de crear y recorrer  92.024.242.230.271.040.357.108.320.801.872.044.844.750.000.000.000 barajas (ordenamientos de cartas) diferentes.

Así que en esta ocasión vamos a afrontar el problema con otra estrategia: simular un número grande de partidas para calcular la frecuencia relativa de victorias. Esta estrategia en algunos ámbitos se conoce como el Método de Montecarlo, pero en nuestro caso podemos simplificar mucho su fundamento como una aplicación de la Ley de los Grandes Números en un experimento de Bernoulli.

 

Imagen creada con IA

 Resumen resumido: si repetimos muuuuchas veces un experimento, la frecuencia relativa de éxito tiende a la probabilidad teórica del suceso.

Así que he creado un programa en Python (ver código) que simula jugar tantas partidas como le indiquemos.

En la estrategia exhaustiva se calculó un ejemplo:

... con un mazo de cartas de 4 números y 4 palos (16 cartas), el número de permutaciones es 63.063.000 (fórmula de las permutaciones con elementos repetidos) y la probabilidad de ganar el juego es aproximadamente 0.011869416297987727 (~1,19%). 

Así que ejecutamos el nuevo código con 4 números y 4 palos e indicamos que queremos que simule 5.000.000 de partidas. Tan sólo 12 segundos más tarde en mi ordenador tengo los resultados:

Se ha ganado el juego 59311 veces de un total de 5000000 partidas.
Porcentaje de éxito: 1.18622 % 

Observamos que es una magnífica aproximación a la probabilidad real calculada con la estrategia exhaustiva.

Vamos entonces a simular el problema original de 13 cartas y 4 palos. Le indicamos que simule 5.000.000 de partidas y los resultados obtenidos en 37 segundos son:

Se ha ganado el juego 81267 veces de un total de 5000000 partidas.
Porcentaje de éxito: 1.62534 %

Pues ya tenemos una aproximación a la solución del problema original. La probabilidad de ganar el juego en las condiciones planteadas es aproximadamente 1,63%.

Subimos el número de partidas simuladas a 10.000.000:

Se ha ganado el juego 162883 veces de un total de 10000000 partidas.
Porcentaje de éxito: 1.62883 % 

Para la precisión que buscamos no varía significativamente. Por lo que nos damos ya por satisfechos con la aproximación de la solución obtenida.

Esta estrategia es estupenda cuando es muy complejo o costoso calcular las soluciones reales, o cuando es suficiente encontrar una aproximación empírica a la solución.

Pero en el problema que nos ocupa, ¿y si subimos la apuesta y encontramos otra manera de solucionar el problema?

Esa será la próxima entrada del blog 😉

Probabilidad con baraja española: manotazo. Solución 1/3 (exhaustiva)

En la entrada anterior planteé una cuestión de probabilidad en un juego de cartas con la baraja española.

¿Cuál es la probabilidad de ganar el juego sin que haya coincidido ninguna vez la carta destapada con el número cantado? 

O su complementario, ¿cuál es la probabilidad de "perder"? Entendemos perder en este contexto como que coincida en algún momento la carta destapada con el número cantado.

Una posible idea es utilizar la estrategia exhaustiva: construir TODAS las posibles barajas (ordenamientos de cartas) y comprobar en cuántas de ellas se gana/pierde el juego. A mano está claro que no lo vamos a hacer, pero ¿podemos hacer un programa que realice esa tarea por nosotros?

He realizado un programa en Python que implementa esta estrategia exhaustiva (ver código).

Por ejemplo, con un mazo de cartas de 4 números y 4 palos (16 cartas), el número de permutaciones es 63.063.000 (fórmula de las permutaciones con elementos repetidos) y la probabilidad de ganar el juego es aproximadamente 0.011869416297987727 (~1,19%). Para crear y recorrer todas las barajas posibles, mi ordenador ha tardado algo menos de 4 minutos y medio.

El problema viene cuando ponemos las condiciones del problema: 13 números y 4 palos. El número de permutaciones (barajas distintas) es:

 92.024.242.230.271.040.357.108.320.801.872.044.844.750.000.000.000

Y, claro, va a llevar muuuuuucho más tiempo llegar a la solución de esa manera.

Así que, una vez más, aunque tengamos un algoritmo que resuelve el problema, la realidad con un ordenador medio es que no es factible llegar a la solución en un tiempo razonable.

¿Habrá alguna estrategia alternativa? A seguir pensando...

 

PD: La librería itertools de Python tiene una función para calcular todas las variaciones de un conjunto, pero no tiene ninguna para hacer lo propio con multiconjuntos (elementos que se repiten). Por ello se ha implementado la función permutaciones_repeticion dentro del programa para evitar repetir ordenamientos ya contados.

 

Polinomios de Laguerre con wxMaxima y Python

Los polinomios de Laguerre son unos polinomios conocidos principalmente (aunque no únicamente) por ser soluciones de la ecuación diferencial

x · y'' + (1 - x) · y' + n · y = 0 

Su nombre se debe al matemático francés Edmond Nicolas Laguerre, quien publicó muchos artículos, principalmente en las áreas de geometría y análisis.

 Una de las formas de calcular los polinomios de Laguerre viene dada por la siguiente expresión:

 

 También se pueden calcular de manera recursiva:

 ;   ;  

En wxMaxima podemos calcular muy fácilmente los polinomios de Laguerre utilizando la función laguerre().

Ejemplo de cálculo de los primeros 5 polinomios de Laguerre:

 En Python también existen maneras de calcular los polinomios de Laguerre, utilizando funciones de las librerías NumPy, SciPy o SymPy.

A modo de ejemplo, el siguiente código calcula y representa gráficamente los primeros polinomios de Laguerre:

# Cálculo y representación gráfica de los polinomios de Laguerre
# Félix Rodríguez Díaz
# 25 de agosto de 2025

import matplotlib.pyplot as plt
from scipy.special import laguerre as laguerre_sci
from numpy import arange
from numpy.polynomial.laguerre import lag2poly
from numpy.polynomial import Polynomial
from sympy.functions.special.polynomials import laguerre as laguerre_sym
from sympy import symbols, Poly

# Definimos la variable n_polinomios con la cantidad de polinomios que
# queremos calcular (desde grado 0 hasta grado n_polinomios-1)
n_polinomios = 5

# Calculamos los polinomios de Laguerre con SciPy
laguerre_scipy = [laguerre_sci(z) for z in range(n_polinomios)]
# Los mostramos por pantalla
print("Polinomios de Laguerre calculados con SciPy")
for lag_s in laguerre_scipy:
    print(lag_s)

# Calculamos los polinomios de Laguerre con NumPy
# Dado que lag2poly devuelve los coeficientes utilizamos Polynomial
# para crear el correspondiente polinomio
laguerre_numpy = [Polynomial(lag2poly([0] * i + [1])) for i in range(n_polinomios)]
# Los mostramos por pantalla
print("\nPolinomios de Laguerre calculados con NumPy")
for lag_n in laguerre_numpy:
    print(lag_n)
    
# Calculamos los polinomios de Laguerre con SymPy
x_sym = symbols("x")
laguerre_sympy = [laguerre_sym(z, x_sym) for z in range(n_polinomios)]
# Los mostramos por pantalla
print("\nPolinomios de Laguerre calculados con SymPy")
for lag_sym in laguerre_sympy:
    print(lag_sym)
# Si queremos representar gráficamente los polinomios de SymPy con pyplot debemos
# convertir las expresiones simbólicas a expresiones que reconozca numpy
laguerre_sympy_numpy = []
for lag_expr in laguerre_sympy:
    # Obtener coeficientes (del término de mayor grado al menor)
    coeffs = Poly(lag_expr, x_sym).all_coeffs()
    # Convertir a float
    coeffs_float = [float(c) for c in coeffs]
    # Invertir para que NumPy los interprete correctamente (menor a mayor grado)
    coeffs_float.reverse()
    # Crear polinomio de NumPy
    poly_numpy = Polynomial(coeffs_float)
    laguerre_sympy_numpy.append(poly_numpy)

# Representamos gráficamente los polinomios
x = arange(-1, 3.5, 0.01)
fig, ax = plt.subplots()
ax.set_title('Polinomios de Laguerre $L_n$')
for n in range(n_polinomios):
    # Utilizamos por ejemplo los calculados con SciPy
    ax.plot(x, laguerre_scipy[n](x), label=f"$L_{n}$")
    # Si quisiéramos utilizar los calculados con NumPy:
    #ax.plot(x, laguerre_numpy[n](x), label=f"$L_{n}$")
    # Si quisiéramos utilizar los calculados con SymPy:
    #ax.plot(x, laguerre_sympy_numpy[n](x), label=f"$L_{n}$")
plt.legend(loc='best')
plt.grid(True)
plt.show()

 Este es el resultado de ejecutarlo:

Los polinomios asociados/generalizados de Laguerre se utilizan en campos como por ejemplo la mecánica cuántica.

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).

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: siguiente, mitad y conserva cifra final 10 veces.

El problema 27 del libro "Ludopatía Matemática" de Mariano Mataix tiene el siguiente enunciado:

Hay que hallar un número tal que si le sumamos una unidad y lo dividimos por 2, el número que resulta termina en la misma cifra que el original.

Repitiendo la operación con el resultado obtenido ocurre lo mismo, es decir, el nuevo número acaba en la misma cifra. Siguiendo así, durante 10 veces se obtiene siempre la misma cifra, pero en la undécima vez ya la terminación es diferente. Un dato más: el número buscado ha de ser el más pequeño que cumple la condición.

Así que igual que en entradas anteriores (1, 2, 3, 4, 5) he construido un algoritmo en Python para resolver el problema. El nivel del problema es facilito para resolver mediante algoritmo.

Ver código en repositorio de GitHub.

El problema 31 plantea una variante del anterior:

Hay que hallar un número tal que si le sumamos una unidad y lo dividimos por 2, el número que resulta termina en una cifra diferente que el original. Repitiendo la operación con el resultado obtenido ocurre lo mismo, es decir, el nuevo número acaba en una cifra diferente. Siguiendo así, durante 10 veces se obtiene siempre una última cifra diferente, pero en la undécima vez ya la terminación es igual. Un dato más: el número buscado ha de ser el más pequeño que cumple la condición.

Ver código en repositorio de GitHub.

Crea cabeceras ASCII para tus programas de terminal

Para crear cabeceras en código ASCII para utilizar por ejemplo en tus programas de consola de texto, en Linux puedes utilizar los siguientes comandos (es posible que tengas que instalarlos en tu distribución): toilet y figlet.

Os pongo dos enlaces por si a alguien le interesa ver ejemplos de su funcionamiento.

Enlace 1          Enlace 2

También puedes llevártelo luego a tu programa de Python y ponerle un poco de estilo :-)

Menor número con un número exacto de divisores

El problema 24 del libro Ludopatía Matemática, de Mariano Mataix Lorda, es el siguiente:

¿Cuál es el menor número con exactamente 100 divisores?

Una vez resuelto con Python podemos aprovechar para generalizar el problema al siguiente:

¿Cuál es el menor número con exactamente m divisores?

He subido a mi repositorio de matematica-recreativa en GitHub una solución utilizando la librería sympy, que calcula los divisores de un número dado (también se puede implementar dicha función fácilmente).

Imagen extraída de joguiba.com

La pregunta es ¿siempre existirá dicho número? Es decir, dado cualquier número natural positivo m, ¿podemos encontrar un natural con exactamente m divisores?

La respuesta es que sí. Si tenemos la factorización en números primos de un número, podemos calcular sus divisores como el producto de los exponentes aumentados en una unidad.

Por ejemplo, el número 18 factoriza de la siguiente manera 18 = 2^1 · 3^2. Si aumentamos los exponentes en una unidad y los multiplicamos obtenemos (1+1) · (2+1) = 2 · 3 = 6. Por lo que el número 18 tiene 6 divisores.

Div(18) = {1, 2, 3, 6, 9, 18}

Por tanto, a la pregunta de si siempre existirá dicho número con exactamente m divisores debemos contestar que sí porque una cota superior siempre será 2^(m-1), que por lo anterior sabemos que tiene m divisores.

¿Podríamos utilizar esto para abordar la programación de la solución desde otro enfoque? ¿Será más rápido, más lento o dependerá del caso?

Si alguien se anima a implementar las dos formas (calculando divisores o utilizando los exponentes de la factorización) para comparar casos que nos cuente sus resultados en los comentarios.

Python: listas VS conjuntos

Imagen creada con IA

En Python, una de las diferencias fundamentales entre los tipos de datos lista (list) y conjunto (set) es que el segundo no puede tener duplicados. De hecho cuando queremos eliminar los duplicados de una lista, una de las maneras de hacerlo es transformar la lista en conjunto y luego volver a pasar el conjunto a lista.

No entro aquí en el tipo de datos que puede contener cada uno de ellos. Si mi variable debe admitir datos duplicados necesariamente debo utilizar una lista. Pero si hay la certeza de que no habrá ningún dato duplicado (o no queremos almacenarlo más de una vez) podemos elegir entre usar una lista o un conjunto. Lo cierto es que la versatilidad de las listas hace que muchas veces nos decantemos por estas, pero no siempre es la mejor opción como mostraré a continuación.

Cuando la cantidad de datos con los que voy a trabajar es considerable, los tiempos de ejecución de los programas puede variar muy significativamente si utilizo listas o si utilizo conjuntos (cuando pueda hacerlo).

¿Hay diferencia en tiempo de ejecución al recorrer una lista y al recorrer un conjunto, ambos con los mismos elementos?

Imagen creada con IA

He hecho una prueba en el ordenador en el que me encuentro escribiendo esta entrada. He creado una lista y un conjunto con los números del 0 al 100000000, este último sin incluir. Recorriendo ambos con un bucle "for ... in" he obtenido los siguientes tiempo de ejecución:

    Tiempo de recorrido en lista: 5.245566 segundos

    Tiempo de recorrido en conjunto: 5.883574 segundos

El tiempo de recorrido sobre el conjunto es aproximadamente un 12% superior al tiempo de recorrido sobre la lista.

Además, en el mismo programa he buscado el elemento 99999999 en la lista (if ... in) y los tiempos de ejecución han sido los siguientes:

    Tiempo de búsqueda en lista: 1.093401 segundos

    Tiempo de búsqueda en conjunto: 0.000001 segundos

El tiempo de búsqueda en el conjunto es muchísimo más corto que el tiempo de búsqueda en la lista y aunque no busquemos el último elemento los tiempos siguen siendo significativamente muy inferiores. Esto en programas con gran cantidad de datos o que debemos realizar muchas búsquedas en una colección de datos puede suponer la diferencia entre un programa con un tiempo de ejecución aceptable o uno de esos que dejas el ordenador encendido y al cabo de muchas horas vuelves para mirar si con suerte ya ha acabado (a mi me pasó con el problema de los cartones del bingo).

A continuación incluyo el código del programa utilizado:

import time

n = 100000000

elementos = list(range(n))

elementoZ = n-1

mi_lista = elementos

mi_conjunto = set(elementos)

# Medir tiempo de recorrido en lista

inicio = time.time()

for elemento in mi_lista:

next

tiempo_lista = time.time() - inicio

# Medir tiempo de recorrido en conjunto

inicio = time.time()

for elemento in mi_conjunto:

next

tiempo_conjunto = time.time() - inicio

print(f"Tiempo de recorrido en lista: {tiempo_lista:.6f} segundos")

print(f"Tiempo de recorrido en conjunto: {tiempo_conjunto:.6f} segundos")

# Medir tiempo de búsqueda en lista

inicio = time.time()

if elementoZ in mi_lista:

tiempo_lista = time.time() - inicio

# Medir tiempo de búsqueda en conjunto

inicio = time.time()

if elementoZ in mi_conjunto:

tiempo_conjunto = time.time() - inicio

print(f"Tiempo de búsqueda en lista: {tiempo_lista:.6f} segundos")

print(f"Tiempo de búsqueda en conjunto: {tiempo_conjunto:.6f} segundos")

Referencia externa sobre el tema: en la documentación de Python, apartado TimeComplexity, se muestra que de promedio una búsqueda "in" en listas tiene orden O(n) y en conjuntos O(1).

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?

Problema de Matemática Recreativa: cartones de bingo especiales

En entradas anteriores (1, 2) he resuelto problemas contenidos en el libro Ludopatía Matemática, de Mariano Mataix Lorda.

Imagen extraída de goodreads.com

El problema 19 se titula Cartones de bingo.

"La figura representa un cartón de bingo algo diferente de los acostumbrados, pero para el caso es igual. Los números de la primera columna se toman de los que existen entre el 1 y el 15, cambos comprendidos; los de la 2.ª, entre el 16 y el 30; los de la 3.ª, entre el 31 y el 45; los de la 4.ª, entre el 46 y el 60; y los de la 5.ª, entre el 61 y el 75.

¿Cuál es el máximo número de tarjetas que pueden hacerse sin que se repita ninguna fila, columna o diagonal?

NOTA: Hay que tener en cuenta que en cada columna el orden de los números va de acuerdo con su magnitud. Es decir, que si, por ejemplo, los números elegidos para la primera columna fuesen 1, 2, 3, 4 y 5, irían en este orden de arriba a abajo, no pudiendo ir nunca un número antes de otro menor que él."

En la próxima entrada pondré mi solución utilitzando Pyhton para continuar con la serie de problemas de matemática recreativa resueltos con programación informática.

Un problema de datos numéricos con Python y numpy para pensar (solución)

  Esta entrada es la continuación de Un problema de datos numéricos con Python y numpy para pensar (enunciado). Si todavía no lo has leído y quieres pensar por ti mismo el problema estás a tiempo :-)

 Resumiendo la entrada anterior: tenemos unos datos en csv, los importamos y los mostramos por pantalla. Observamos en pantalla varios datos que tienen valor 9. pero al contar la cantidad de datos que son mayores o iguales que 9 el programa devuelve 0.

 Quedó la pregunta abierta para que quien quisiera pensara el posible motivo y en esta entrada explico lo que estaba sucediendo.

Imagen de centrotadi.com

 La importación desde el csv es correcta, así como también la definición del array/matriz. El problema es que al mostrarlo por pantalla los datos se desvirtúan y pierden precisión.

El csv en realidad contiene la siguiente información:

1.999999999999990,7.999999999999990,7.999999999999990,1.999999999999990,8.999999999999989,3.999999999999990,0.999999999999990,1.999999999999990,1.999999999999990,0.999999999999990
6.999999999999990,6.999999999999990,1.999999999999990,7.999999999999990,5.999999999999990,5.999999999999990,3.999999999999990,2.999999999999990,7.999999999999990,8.999999999999989
4.999999999999990,3.999999999999990,5.999999999999990,1.999999999999990,0.999999999999990,5.999999999999990,1.999999999999990,5.999999999999990,5.999999999999990,2.999999999999990
3.999999999999990,6.999999999999990,5.999999999999990,0.999999999999990,0.999999999999990,8.999999999999989,8.999999999999989,4.999999999999990,5.999999999999990,5.999999999999990
1.999999999999990,3.999999999999990,5.999999999999990,7.999999999999990,0.999999999999990,6.999999999999990,5.999999999999990,3.999999999999990,7.999999999999990,6.999999999999990
7.999999999999990,0.999999999999990,5.999999999999990,2.999999999999990,4.999999999999990,6.999999999999990,8.999999999999989,4.999999999999990,3.999999999999990,0.999999999999990
6.999999999999990,2.999999999999990,6.999999999999990,0.999999999999990,0.999999999999990,3.999999999999990,4.999999999999990,8.999999999999989,2.999999999999990,6.999999999999990
5.999999999999990,3.999999999999990,5.999999999999990,0.999999999999990,6.999999999999990,1.999999999999990,8.999999999999989,4.999999999999990,2.999999999999990,5.999999999999990
6.999999999999990,7.999999999999990,2.999999999999990,1.999999999999990,7.999999999999990,2.999999999999990,0.999999999999990,4.999999999999990,1.999999999999990,1.999999999999990
2.999999999999990,3.999999999999990,7.999999999999990,2.999999999999990,6.999999999999990,6.999999999999990,1.999999999999990,0.999999999999990,5.999999999999990,8.999999999999989

 Y podemos observar que en realidad no hay ningún dato mayor o igual que 9, por lo que el programa no estaba fallando. Lo que fallaba era nuestra visualización de los datos.

Esto me sucedió realizando otro programa más complejo y me costó dar con la clave. Para centrarme en el problema real he diseñado este otro programa mucho más sencillo, que se puede utilizar a modo de problema.

 ¡Ojo! Otro fallo que se puede cometer es al ver por pantalla que los datos se muestran como float pero vemos que son enteros trabajar con ellos pasándolos a enteros con int. El resultado de hacer eso cambiaría completamente los datos, dado que al hacer int truncamos el número y por ejemplo 1.999999999999990 pasa a ser 1.

 En este caso, si queremos hacer una conversión a entero, lo correcto es utilizar redondeo (round). Podríamos modificar el código de la siguiente manera:

import numpy as np
from random import choice

# Importamos los datos del archivo CSV
M = np.genfromtxt("datos-ir.csv", delimiter = ",")

print("La matriz importada es: ")
print("M =\n" , M)

print("\nCreamos una matriz donde cada elemento es True si el correspondiente")
print("elemento de la matriz original es mayor o igual que 9 y False en otro caso")

N = (np.round(M,0) >= 9)

print("N =\n", N)
print("\nLa cantidad de True en la nueva matriz es: ", N.sum())

Un problema de datos numéricos con Python y numpy para pensar (enunciado)

Tenemos unos datos numéricos en un archivo CSV. Importamos dichos datos y los mostramos por pantalla:

[[2. 8. 8. 2. 9. 4. 1. 2. 2. 1.]
[7. 7. 2. 8. 6. 6. 4. 3. 8. 9.]
[5. 4. 6. 2. 1. 6. 2. 6. 6. 3.]
[4. 7. 6. 1. 1. 9. 9. 5. 6. 6.]
[2. 4. 6. 8. 1. 7. 6. 4. 8. 7.]
[8. 1. 6. 3. 5. 7. 9. 5. 4. 1.]
[7. 3. 7. 1. 1. 4. 5. 9. 3. 7.]
[6. 4. 6. 1. 7. 2. 9. 5. 3. 6.]
[7. 8. 3. 2. 8. 3. 1. 5. 2. 2.]
[3. 4. 8. 3. 7. 7. 2. 1. 6. 9.]]
 

Vemos que se trata de una matriz de 10x10 con números entre 1 y 9 (incluidos).

Creamos otra matriz de manera que un elemento es True si el correspondiente elemento de la matriz original es mayor o igual que 9 y False en caso contrario. Finalmente contamos la cantidad de True en la nueva matriz.

Es decir, en realidad con el procedimiento anterior estamos contando cuántos elementos de la matriz original son iguales o mayores que 9.

En la pantalla vemos que hay varios 9 en los datos originales, sin embargo la matriz creada no tiene ningún True (ver más abajo la salida del programa). Es decir, el procedimiento concluye que en la matriz original no hay ningún 9. ¿Cómo es esto posible? ¿Dónde está el fallo?

La respuesta la subiré próximamente en otra entrada. Mientras tanto podéis poner vuestras hipótesis en los comentarios.

 

El código del programa es el siguiente

import numpy as np
# Importamos los datos del archivo CSV
M = np.genfromtxt("datos-ir.csv", delimiter = ",")
print("La matriz importada es: ")
print("M =\n" , M)
print("\nCreamos una matriz donde cada elemento es True si el correspondiente")
print("elemento de la matriz original es mayor o igual que 9 y False en otro caso")
N = (M >= 9)
print("N =\n", N)
print("\nLa cantidad de True en la nueva matriz es: ", N.sum())

 

La salida del programa es la siguiente:

La matriz importada es:  
M =
[[2. 8. 8. 2. 9. 4. 1. 2. 2. 1.]
[7. 7. 2. 8. 6. 6. 4. 3. 8. 9.]
[5. 4. 6. 2. 1. 6. 2. 6. 6. 3.]
[4. 7. 6. 1. 1. 9. 9. 5. 6. 6.]
[2. 4. 6. 8. 1. 7. 6. 4. 8. 7.]
[8. 1. 6. 3. 5. 7. 9. 5. 4. 1.]
[7. 3. 7. 1. 1. 4. 5. 9. 3. 7.]
[6. 4. 6. 1. 7. 2. 9. 5. 3. 6.]
[7. 8. 3. 2. 8. 3. 1. 5. 2. 2.]
[3. 4. 8. 3. 7. 7. 2. 1. 6. 9.]]

Creamos una matriz donde cada elemento es True si el correspondiente
elemento de la matriz original es mayor o igual que 9 y False en otro caso
N =
[[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]]

La cantidad de True en la nueva matriz es:  0

 

Un problema de criptoaritmética diferente

 En la anterior entrada hablé sobre los criptoaritmos y cité el libro Ludopatía Matemática, de Mariano Mataix Lorda.

 En dicho libro aparece un criptoaritmo diferente a los habituales. Se trata del siguiente problema:

 Resulta que entre TEN y TWENTY hay ONE cuadrados perfectos. Por otra parte, TWO, TEN, TWELVE y TWENTY son pares, con la particularidad de que tanto el último como el primer dígito de TWENTY son pares. Por último, TEN no es divisible por 3. ¿Cuánto vale NOW?

Imagen extraída de www.conmishijos.com

  Aquí está mi propuesta de resolución con Python, utilizando la estrategia del método exhaustivo (comprobar todas las posibles soluciones).

 

 

Criptoaritmos con Python

El otro día abrí el libro Ludopatía Matemática, de Mariano Mataix Lorda. En este libro se pueden encontrar diferentes pasatiempos, juegos y curiosidades relacionadas con las matemáticas.

Imagen extraída de goodreads.com

 

Algunos de ellos son los conocidos criptoaritmos. Podemos decir, de manera simple, que un criptoaritmo (o criptograma aritmético) es una operación aritmética en la que han cambiado los dígitos de los números implicados en la operación por letras y debemos averiguar qué dígito le corresponde a cada letra para que la operación se cumpla.

Por ejemplo (número 1 del citado libro y que aparece en la portada):

Las cifras han sido cambiadas en la siguiente suma
    YZRM
    BRCP
    TPRM
    BTCP
    XLXX

 Las condiciones más habituales en este juego son las siguientes:

- Cada letra corresponde a un dígito diferente.
- Por tanto, no puede haber más de 10 letras diferentes.
- El primer carácter de cada número no puede equivaler a 0.

Hay diferentes maneras de plantear matemáticamente estos problemas, pero hoy no quiero entrar en esa parte sino en que es un problema que puede resolverse "fácilmente" probando posibilidades hasta que una cuadre.

Imagen extraída de fotogramas.es

¿Cómo vamos a probar posibilidades hasta encontrar la correcta? ¿Eso no es demasiado trabajo? Bueno, tampoco hace falta que las probemos manualmente. Es decir, podemos desarrollar un programa que compruebe todas las soluciones por nosotros. Y, además, que nos sirva no sólo para resolver el criptoaritmo del ejemplo sino cualquier criptoaritmo que cumpla las condiciones dadas.

Y ya que estamos, que no sólo resuelva criptoaritmos de sumas sino también criptoaritmos que utilicen suma, resta, multiplicación y/o división.

Imagen extraída de lamardemates.blogspot.com

Para ello he desarrollado en Python dos versiones de un "resolutor de criptoaritmos", siguiendo dos estrategias:

- Una que he llamado probabilística: consiste en ir asignando al azar valores a las letras hasta encontrar la que hace que se cumpla la operación. Código aquí.

- Otra que he llamado exhaustiva: consiste en ir comprobando todas las posibles asignaciones de valores a las letras hasta encontrar la que hace que se cumpla la operación. Código aquí.

Nota: a nivel de programación, en los códigos se pueden mejorar varias cosas, pero para el objetivo que persigo en esta entrada lo doy por bueno.

¿Qué ventajas puede tener la estrategia probabilística?

- No es necesario programar una estrategia de combinatoria.

- Puede haber suerte y que al azar encuentre la solución más rápido.

¿Qué desventajas tiene?

- Si no tiene solución entramos en un bucle infinito (se puede poner un número máximo de bucles y decir que es probable que no tenga solución).

- Puede repetir más de una vez la misma combinación, por lo que estaría haciendo cálculos repetidos innecesarios.

- Igual que puede haber suerte y encontrar rápido la solución, también puede tardar más en encontrar la solución. Es una cuestión de azar.

Imagen extraída de es.123rf.com

¿Por qué es útil entonces conocer la estrategia probabilística? Porque en ocasiones no conocemos el patrón que rige el problema, no sabemos implementar correctamente la estrategia exhaustiva o no tenemos tiempo/ganas para implementarla. No me refiero sólo a criptoarimética, sino como estrategia general de resolución de problemas mediante computación.