El problema de la mochila (II)

Aplicamos un algoritmo genético para introducir en la mochila el mayor número de objetos que maximicen el beneficio pero sin superar la restricción de peso de la misma. En la tabla se muestra el problema a resolver: 4 objetos con diferentes utilidades y pesos.

La función objetivo Z no puede contener los 4 objetos pues rebasaría la restricción del peso que no puede superar el valor 15.

$$Z=4x_1+5x_2+6x_3+3x_4$$

$$P=7x_1+6x_2+8x_3+2x_4 \leq 15$$

Un cromosoma está formado por genes que son variables binarias. Cada cromosoma estará formado por una cadena de 4 bits. Si la suma de pesos de un cromosoma rebasa el peso máximo permitido 15, no se considera.

En la Tabla se muestran 4 cromosomas aleatorios de los cuales se tienen que obtener dos padres. La penúltima columna de probabilidad se obtiene dividiendo cada peso entre el total, y en la última columna la probabilidad acumulada.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.477) que supera a la probabilidad acumulada 0.2973; así el Padre 1 será el cromosoma 2: 1 0 1 0.
Se genera otro número aleatorio (0.934) que supera a la probabilidad acumulada 0.7027; así el Padre 2 será el cromosoma 4: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98.  Se genera un número aleatorio 0.735<0.98 y entonces hay cruzamiento. Como hay 4 genes hay tres puntos de corte entre genes. Se genera otro número aleatorio (0.492). Como 1/3<0.492<2/3, el punto de corte está entre el gen 2 y el gen 3 (línea discontinua). Entonces se intercambian los genes 3 y 4.

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. Los genes en rojo se han cambiado. Como el segundo cromosoma rebasa la restricción se elimina. Por tanto, hasta el momento, sólo hemos obtenido un hijo.

Repetimos el proceso, manteniendo la tabla inicial, para obtener nuevos hijos.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.802) que supera a la probabilidad acumulada 0.7027; así el Padre 1 será el cromosoma 4: 0 1 1 0.
Se genera otro número aleatorio (0.266) que no supera a la probabilidad acumulada 0.2973; así el Padre 2 será el cromosoma 1: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98. Se genera un número aleatorio 0.174<0.98 y entonces hay cruzamiento. Como hay 4 genes hay tres puntos de corte entre genes. Se genera otro número aleatorio (0.740). Como 2/3<0.7401, el punto de corte está entre el gen 3 y el gen 4 (línea discontinua). Entonces se intercambia el gen 4.

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. Los genes en rojo se han cambiado. Como el primer cromosoma rebasa la restricción se elimina. Por tanto sólo hemos obtenido un segundo hijo.

Volvemos a repetir el proceso para conseguir los dos hijos que faltan.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.658) que supera a la probabilidad acumulada 0.5676; así el Padre 1 será el cromosoma 3: 0 1 0 0.
Se genera otro número aleatorio (0.258) que no supera a la probabilidad acumulada 0.2973; así el Padre 2 será el cromosoma 1: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98. Se genera un número aleatorio 0.989>0.98 y entonces no hay cruzamiento. 

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. El gen en rojo se ha cambiado. Como los dos cromosoma cumplen la restricción se aceptan. Por tanto ya tenemos los 4 hijos.

Termina la primera iteración y vamos a iniciar la segunda iteración con estos 4 hijos. Para ello tomamos estos 4 hijos como cromosomas iniciales y construimos una nueva tabla.

Si suponemos que esta tabla es la obtenida después de varias iteraciones podemos considerar que representa los resultados finales donde los objetos a considerar para la mochila son el 2 y el 3 con una utilidad máxima de 11 y un peso de 14.

El problema de la mochila (I)

El problema de la mochila (knapsack problem) es el siguiente problema de optimización combinatoria:

  Dado un conjunto de elementos, cada uno con un peso y un valor, determinar qué elementos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea el mayor posible.

El problema más sencillo (0-1 knapsack problem) es aquel en el que se restringe el número de copias de cada item a cero o uno.

Si n es el número de items numerados de 1 a n, cada uno con un peso wi y un valor vi, con una capacidad máxima de peso W, se trata de maximizar:

$$\sum_{i=1}^n v_ix_i$$

con la restricción:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \}$$

El problema de la mochila acotada (BKP) elimina la restricción de que solo exista un ejemplar de cada artículo, pero restringe el número xi de copias de cada tipo de artículo a un valor entero máximo no negativo c. Por tanto la restricción es:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \dots c\}$$

El problema de la mochila ilimitada (UKP) no impone un límite superior al número de copias de cada tipo de artículo y  la única restricción de xi es que sea un número entero no negativo:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in N$$

Vamos a resolver un ejemplo mediante programación dinámica:

Sean 5 objetos con los valores vi y pesos wi que se muestran en la Figura. Los pesos posibles en la mochila van desde 0 al máximo permitido de W=8 .

 Se establece una matriz M[i,j] donde cada elemento indica el beneficio máximo de llevar una mochila de peso j con objetos desde x1 hasta xi.

La primera fila de ceros corresponde  a no meter ningún objeto en la mochila y la primera columna de ceros indica mochila de tamaño cero que no admite ningún objeto.

Analicemos el funcionamiento observando las celdas coloreadas.  La matriz se va completando de izquierda a derecha y de arriba a abajo. Si estamos en la celda M[3,5]=7, retrocedemos 4 posiciones hasta la celda M[2,0]=0 ya que w3=4; ahora hacemos el cálculo siguiente:

$$M[3,1]+v_3=0+10=10>M[3,5]=7 \rightarrow M[4,5]=10$$

La celda M[5,5] también  vale 10 porque una mochila de peso máximo 4 no admite un objeto de peso 5.

La celda M[6,8] repite el valor 16 pues el valor que se obtiene (15) es menor que el de su celda superior.

El valor más alto de la última columna (19) indica el valor máximo.

Vamos a obtener los objetos con los que se consigue el valor máximo:

Al ser M[6,9]=M[5,9] el objeto W5=7 no se pone en la mochila. Como M[5,9]>M[4,9] el objeto w4=5 se pone en la mochila.

Retrocedemos 5 posiciones a  M[4,4] y siguiendo el mismo razonamiento no ponemos el objeto w3=4 y si ponemos el objeto w2=3. Continuando el proceso se llega a M[2,1]=0 y finaliza rl proceso.

Se han colocado en la mochila el objeto w2=3, v2=5 y el objeto w4=5, v4=14.

Problema del cambio de moneda (II)

Se trata de, dada una serie de monedas, devolver una cantidad determinada usando el menor número posible. Vamos a aplicar la Programación Dinámica para evitar los errores que se pueden producir utilizando un Algoritmo Voraz.

Existen n monedas diferentes y con una cantidad ilimitada de cada tipo: $$X_1 < X_2 < X_3 \cdots < X_n$$

Se trata de devolver una cantidad c, donde cambio(n,c) indica las mínimas monedas necesarias para devolver c usando X1, X2, X3,...Xn monedas.

• Si Xn>c no usamos esa moneda y cambio(n,c)=cambio(n-1,c).
• Si Xn<=c podemos usar esa moneda o no.
• Si usamos Xn entonces cambio(n,c-Xn)+1.
• Si no usamos Xn entonces cambio(n-1,c).
• De las dos opciones cogemos la menor cantidad.

Vamos a establecer una tabla con una matriz M((i,j)=cambio(i,j) donde i indica el número total de monedas <=Xi para devolver la cantidad j. Entonces cambio(i,j) es: $$cambio(i-1,j) \hspace{0.1 cm}si \hspace{0.1 cm} X_i>j$$ $$min(cambio(i-1,j),cambio(i,j-X_k)+1) \hspace{0.2 cm} si X_i\leq j$$

En la tabla la primera fila está numerada de 0 a c y la primera columna con los valores de las monedas incluida la posibilidad de no tener monedas. La primera columna de ceros indica que no se necesita ninguna moneda para devolver cero. La fila de infinitos indica que sin monedas no podemos devolver ninguna cantidad. La columna de infinitos indica que no podemos devolver 1 con monedas de valor superior. 

Vamos a explicar como se obtiene el elemento M(3,7) (verde) de la matriz. Para ello utilizamos los elementos M(2,7) M(3,4) (rojos) $$cambio(3-1,7)=M(2,7)=3 \hspace{0.2 cm} cambio(3,7-3)+1=M(3,4)+1=2$$ Al ser M(2,7)=3 se retroceden 3 posiciones desde la columna 7. De los dos valores obtenidos el menor es el que se asigna al elemento M(3,7). El razonamiento seguido, para todos los demás elementos de la matriz, es el mismo. El último elemento M(4,9) indica el número de monedas necesaria. 

  ¡Por tanto la solución óptima utiliza 3 monedas!

Vamos a ver el reparto de esas tres monedas. Para ello aplicamos el algoritmo siguiente: $$ si \hspace{0.2 cm} i>2 \land M(i,j)=M(i-1,j) \rightarrow i=i-1$$ $$ si \hspace{0.2 cm} no \rightarrow N(i)=N(i)+1 \land j=j-X_i$$

Empezamos en el último elemento M(4,8). Como M(4,8)=M(3,8)=3 subimos una fila y ahora M(3,8)=3<>M(2,8)=4 entonces el contador de monedas de valor 3 es N(3)=1 y retrocedemos 8-3 columnas y se repite el proceso a partir del elemento M(3,5) (verde) consiguiendo una segunda moneda de 3 y finalmente una moneda de 2.

¡Por tanto con 2 monedas de 3 y una de 2 se devuelve la cantidad 8 !

Problema del cambio de moneda (I)

Dado un monto M de monedas y un conjunto de denominaciones D (billetes o monedas) se busca la mínima cantidad de denominaciones cuya suma sea M.

No existen restricciones sobre el número de billetes o monedas de una denominación y sobre el uso repetido de billetes o monedas.

Vamos aplicar un algoritmo voraz: se elige la opción óptima en cada paso con la esperanza de llegar a una solución general óptima.

Sea un monto de M=36 monedas y denominaciones D={1,2,5,10,20}. Se elige en cada paso la mayor moneda posible y así sucesivamente:

• paso 1: 36-20=16
• paso 2: 16-10=6
• paso 3: 6-5=1
• paso 4: 1-1=0

Por tanto la solución general es: S={20,10,5,1} que suman 36. Además es óptima porque no existen otra solución con menos monedas. 

No siempre la suma de las soluciones óptimas de cada paso dan una solución óptima general. Si ahora las denominaciones son D={1,2,5,10,18,20} también se tiene:

• paso 1: 36-20=16
• paso 2: 16-10=6
• paso 3: 6-5=1
• paso 4: 1-1=0

Sin embargo la solución óptima es: S={18,18} que también suman 36. Aunque a veces puede no fallar, por ejemplo, si el monto es M=39:

• paso 1: 39-20=19
• paso 2: 19-18=1
• paso 3: 1-1=0

Por tanto la solución general es: S={20,18,1} que suman 39. 

Para que el algoritmo no falle nunca es necesario que cada clase de moneda sea igual o mayor que una sucesión de potencias. No puede haber dos clases de monedas que cumplan la misma condición. $$k^0,k^1,k^2,\cdots k^n$$ En nuestro ejemplo válido: $$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20$$ En las monedas del euro se cumple este criterio: $$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20,2^5\leq50,2^6\leq100$$ 

 Para que no falle nunca se utiliza la Programación Dinámica.

Magia con cartas (II)

DESARROLLO

• El mago entrega la baraja de cartas a un espectador y le pide que la baraje. El espectador devuelve la baraja al mago quien mira discretamente la carta que se encuentra en la parte inferior.
• El mago escribe en un papel, sin que nadie vea, la carta que visualizó. Dobla este papel varias veces y pide al espectador que lo guarde en un bolsillo.
• El mago saca doce cartas de la parte superior del mazo, boca abajo, y las coloca sobre una mesa. Luego, el mago pide al espectador que elija, al azar, cuatro de estas cartas y les dé la vuelta dejando sus caras visibles y recuerde cuáles son. Las cartas restantes las recoge el mago y las coloca en la parte inferior del mazo restante.
• El mago explica al espectador que colocará cartas, boca abajo, sobre cada una de las cuatro que eligió. El número de cartas colocadas será igual a la diferencia entre el número 10 y el valor de la carta elegida. Por ejemplo, el mago colocará siete cartas sobre una carta que es un tres, contando en voz alta: 4, 5, 6, 7, 8, 9, 10. Si se ha elegido una de las figuras (K, Q, J), no se repartirán cartas, ya que, en este truco, las figuras cuentan como diez.
• El mago pide al espectador que sume los valores de las cuatro cartas que eligió inicialmente.
• El mago descarta del mazo restante el número de cartas correspondientes a esta suma, creando un montón sobre la mesa. Muestra la carta que estaba encima de esa pila.
• El mago pide al espectador que saque del bolsillo el papel que le habían entregado al principio y confirme si coincide con la carta que le entregó. ¡Y coinciden!

EXPLICACIÓN

Al recoger las ocho cartas y colocarlas en la parte inferior del mazo coloca la carta que miró el mago en la posición 40. Después de repartir correctamente las cartas y sumar los valores de las cuatro cartas boca arriba, la cuenta recaerá invariablemente en esta carta. ¡La cuenta termina en la novena carta desde el final del mazo!

Si el número de las 4 cartas es:  $$n_1, n_2, n_3, n_4$$

El número de cartas colocadas serán: $$10-n_1+10-n_2+10-n_3+10-n_4=40- (n_1+n_2+n_3+n_4)$$

Al quitar ahora del mazo: $$n_1+n_2+n_3+n_4=40$$

Es decir, la solución es la última carta que ha puesto en el montón, la que está en la posición 40.

Triangulación de polígonos

Si triangulamos un pentágono, existen cinco formas diferentes de hacerlo. Si nos fijamos en el número de triángulos que comparten un vértice, podemos asignar ese número a cada uno de ellos. Como las cinco figuras se obtienen por rotación de 72º, sólo existe una secuencia de números.

Vamos a construir una cadena infinita de números de la siguiente manera:

Una primera fila de unos y una segunda fila con la secuencia de los vértices repetida de forma indefinida en la posición de los espacios vacíos de la primera fila. La segunda fila se obtiene aplicando la 'regla del diamante':

Se siguen completando filas hasta llegar a otra vez a una fila de unos.  Se observa que hay dos filas entre las filas de unos.

En el caso del hexágono es más complejo pues hay varias formas de triangularlo. Los seis primero tienen una secuencia válida para todos pues basta hace rotaciones de 60º.

Se observa que se necesitan tres filas hasta llegar de nuevo a la fila de unos. 

Ahora se hace una triangulación en zig-zag y existen dos secuencias diferentes pero que también necesitan tres filas hasta llegar a la fila de unos.

Por último hay otro tipo de triangulación con sólo dos casos. Como en todo hexágono se necesitan tres filas hasta llegar a la fila de unos.

En los polígonos de 3 y 4 lados observamos que en el triángulo ya se obtienen los unos al introducir la secuencia de vértices y en el caso del cuadrado sólo hay una fila entre las filas de unos.

El número de triangulaciones aumentan según los lados del polígono siguiendo la serie de los números de Catalan: 1, 2, 5, 14, 42, 132, 429, 1430, 4862 .... Vemos que se necesitan 0, 1, 2 y 3 filas para partiendo de una fila de unos llegar a otra fila de unos. La fórmula general es F=N-3, siendo F el número de filas y N el número de lados del polígono. 

Por tanto,  se puede conseguir con cualquier polígono  como  demostró  el Teorema de Coxeter-Conway. A este tipo de secuencias le llamó Coxeter 'Frieze Patterns'.

Magia con cartas (I)

PREPARACIÓN

Previamente y sin el conocimiento de los espectadores, el mago coloca, desde la parte superior de la baraja, y con las caras hacia abajo, nueve cartas según la siguiente secuencia: 7 3 5 4 9 2 A 6 8.

El palo no tiene importancia. Esta secuencia se puede cambiar, sin embargo, se debe asegurar que la suma de los valores de las tres primeras cartas sea igual a 15, así como la suma de los tríos siguientes. El mago también debe introducir el código 1665 en el candado.

DESARROLLO

• El mago pide prestado al público un objeto, un anillo o un llavero, algo que pueda sujetar a su candado. Después de hacerlo, cambia la combinación discretamente. Le entrega el candado a un espectador y le pide que cambie aleatoriamente los números de la combinación. El candado podrá permanecer en posesión de este último espectador hasta el final del truco.
• Luego, el mago solicita la participación de otros tres espectadores. Distribuye las nueve cartas, que están en la parte superior del mazo, entre los tres voluntarios, siempre boca abajo. Las tres primeras cartas se entregan al primer espectador, las tres siguientes al segundo y las restantes al tercero. Cada espectador puede barajar sus tres cartas.
• El mago dice que los tres espectadores le ayudarán a descubrir el código que le permitirá abrir la cerradura y recuperar el objeto prestado. Para ello, el mago tendrá que sumar tres números, de tres dígitos, que serán presentados por los espectadores con ayuda de las cartas que tengan en la mano. Antes de iniciar todo el procedimiento, el mago pide a los voluntarios que decidan, entre ellos, quién proporcionará las centenas, las decenas y las unidades.
• Después el mago se dirige a una pizarra. Le pide al 'espectador de las centenas' que elija una de sus cartas y anuncie su valor. El mago afirma que esta carta debe descartarse. El mago anota el número anunciado en la pizarra y pide al 'espectador de las decenas' y luego al 'espectador de las unidades' que hagan lo mismo. Cada espectador tiene dos cartas en la mano y en el tablero está grabado un número de tres cifras. El mago repite el procedimiento hasta que se queda sin cartas. Los tres números grabados en la pizarra deben estar alineados para que se puedan sumar con el algoritmo de suma habitual.
• El mago suma los tres números. El mago anuncia al público que la suma obtenida (1665) podría ser la combinación del candado y luego pide al espectador, que lo tiene consigo, que introduzca este código. ¡Y  el candado se abre! ¡MAGIA!

EXPLICACIÓN

Consideremos las 9 cartas: $$a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2,c_3$$ sabiendo que están preparadas para que: $$a_1+a_2+a_3=15 $$ $$b_1+b_2+b_3=15 $$ $$c_1+c_2+c_3=15 $$

 Al sumar podemos tener la siguiente situación:

Independientemente de las permutaciones de las cartas de cada espectador, la suma obtenida siempre será 1665, ya que el algoritmo de suma utilizado se realiza por columnas.

Otras formas de multiplicar

EL MÉTODO EGIPCIO

Es un método por duplicación que sólo necesita saber sumar. Para multiplicar A·B, en una columna se escriben las sucesivas potencias de 2: 1,2,4,8,16,... mientras sean números menores que B. La otra columna se obtiene duplicando los valores a partir de A. Así mediante suma de potencias de 2, siempre se puede obtener el multiplicador B. Se buscan los números correspondientes de la otra columna y sumándolos se obtiene el producto A·B.

En la imagen se muestra un ejemplo, donde se puede ver el criterio a seguir para seleccionar las potencias de 2 necesarias para obtener el producto de A·B.

EL MÉTODO HINDÚ

Este algoritmo, también conocido como de las 'celosías' fue originado en la India y transmitido a China y Arabia llegando a Italia durante los siglos XV y XVI. Se construye una caja rectangular dividida en celdas cuadradas que a su vez están partidas por la mitad, como se observa en la figura. Encima de la caja se sitúan las cifras del multiplicando y a la derecha las del multiplicador.

Se multiplica cada cifra del multiplicando por cada una del multiplicador situando el resultado en la celda cuadrada correspondiente, separando las decenas de las unidades. Se hacen las sumas diagonales que van dando las diferentes cifras del producto, teniendo en cuenta que si una suma es de dos dígitos, las decenas se añade a la suma diagonal siguiente.

EL MÉTODO VÉDICO

La matemática védica de Bhárati Krishná Tirthá es un sistema de cálculo mental desarrollado por Shri Bhárati Krishná Tirtháji a mediados del siglo XX quien dijo haberse basado en el Átharva Vedá, un antiguo texto de los Vedás (los cuatro textos más antiguos de la literatura india). Vamos a analizar la multiplicación con este método.

En la figura los puntos representan cada una de las cifras, correspondiendo los de la primera línea al multiplicando y los de la segunda al multiplicador. Las líneas indican qué cifras son las que hay que multiplicar y sumar para obtener las cifras del producto. Si el resultado es de dos dígitos, la cifra de las decenas se suma a la operación siguiente.

EL MÉTODO JAPONÉS

Aunque se cree que fue inventado por los mayas, recibe este nombre porque lo utilizan los maestros japoneses para enseñar a sus alumnos. En este método se dibujan grupos de líneas verticales que indican las cifras del multiplicando y grupos de líneas horizontales que indican las cifras del multiplicador y se señalan los puntos de intersección, como se muestra en la imagen.

Se forman cuatro grupos de puntos (separados por las líneas discontinuas) y el número en cada grupo indica una de las cifras del producto. Se empieza con las unidades situadas en la parte inferior derecha de la imagen. Si el resultado es de dos dígitos, la cifra de las decenas se suma a la operación siguiente.

Sucesiones de 'Somos'

Estas sucesiones deben su nombre a su creador, el matemático americano Michael Somos.

 Con la relación de recurrencia: $$a_n=a_{n-1} \wedge a_0=1$$ se obtiene la sucesión Somos-1: $$1,1,1,1,1,\ldots$$

Con la relación de recurrencia:

$$a_n=\frac{a_{n-1}^2}{a_{n-2}} \wedge a_0,a_1=1$$ se obtiene la sucesión Somos-2: $$1,1,1,1,1,\ldots$$

Con la relación de recurrencia:

$$a_n=\frac{a_{n-1}a_{n-2}}{a_{n-3}} \wedge a_0,a_1,a_2=1$$ se obtiene la sucesión Somos-3: $$1,1,1,1,1,\ldots$$

Vemos que los elementos semilla de la sucesión son siempre 1 y que el número de éstos coincide con el orden de la sucesión y que todas la sucesiones son iguales.

Con la relación de recurrencia:

$$a_n=\frac{a_{n-1}a_{n-3}+a_n^2}{a_{n-4}} \wedge a_0,a_1,a_2,a_3=1$$

 se obtiene la sucesión Somos-4: 

$$1,1,1,1,1,2,7,23,59,314,1529,8209,83313,620297,7869898\ldots$$

Se observa que la sucesión crece muy rápido pero siempre con valores enteros a pesar que en la fórmula de recurrencia hay un denominador.

Con la relación de recurrencia:

$$a_n=\frac{a_{n-1}a_{n-4}+a_{n-2}a_{n-3}}{a_{n-5}} \wedge a_0,a_1,a_2,a_3,a_4=1$$ se obtiene la sucesión Somos-5:

$$1,1,1,1,1,2,3,5,11,37,83,274,1217,6161,22823,165713 \ldots$$

La sucesión Somos-6 es:

$$1,1,1,1,1,1,3,5,9,23,75,37,421,1103,5047,41873,281527 \ldots$$

La sucesión Somos-7 es:

$$1,1,1,1,1,1,,3,5,9,17,41,137,769,1925,7203,340821 \ldots$$

Vemos que estas sucesiones siguen dando siempre valores enteros. ¿Se romperá esto alguna vez y aparecerá un número fraccionario?

Con la relación de recurrencia:

$$a_n=\frac{a_{n-1}a_{n-7}+a_{n-2}a_{n-6}+a_{n-3}a_{n-5}+a_{n-4}^2a}{a_{n-8}} \wedge a_0,a_1,a_2,a_3,a_4,a_5=1$$

se obtiene la sucesión Somos-8:

$$1,1,1,1,1,1,1,1,4,7,13,25,61,187,775,5827,14815, \ldots$$

Calculamos el siguiente término:

$$a_{17}=\frac{a_{16}a_{10}+a_{15}a_{11}+a_{14}a_{12}+a_{13}^2}{a_9}=$$ $$\frac{14815\cdot 13+5827 \cdot 25+775 \cdot 61+ 187^2}{7}=\frac{420514}{7}$$

Hemos tenido que llegar a es término de Somos-8 para que aparezca un número no entero. 

 Todas estas sucesiones se deducen de una fórmula general: $$a_n=\frac{\sum_{i=1}^{\lfloor k/2 \rfloor}a_{n-i}a_{n-(k-i)}}{a_{n-k}}$$ $$a_i=1 \hspace{0.5 cm}i=0,\ldots k-1$$ El símbolo superior del sumatorio indica 'parte entera'. Las siguientes sucesiones Somos obtienen el primer término fraccionario en posiciones cada vez más avanzadas: $$k=9,10,11, 12,13,14,15, \ldots \rightarrow a_{19},a_{20},a_{22},a_{24},a_{27},a_{28},a_{30},\ldots$$

Períodos de Pisano

Leonardo de Pisa o Leonardo Pisano es conocido como Fibonacci, hijo de Bonacci, que era el apodo de su padre. De ahí el nombre de Períodos de Pisano a los obtenidos de la sucesión de Fibonacci.
La operación módulo da el resto de una división entera: $$14 \mod 3 =2$$ donde 2 es el resto de dividir 14 entre 3.

Para la sucesión de Fibonacci: $$0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181...$$ la sucesión de restos, es siempre periódica: $$F_i \mod n$$

• restos modulo 2: $$0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1...$$
• restos modulo 3: $$0,1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0,1,1,2,0,2,2,1...$$
• restos modulo 4: $$0,1,1,2,3,1,0,1,1,3,2,1,0,1,1,3,2,1,0,1,1,2,3,1...$$
• restos modulo 5: $$0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2...$$
• restos modulo 6: $$0,1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,3,1,4,5,3,2,5,1...$$
• restos modulo 7: $$0,1,1,2,3,5,1,6,1,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1...$$
• restos modulo 8: $$0,1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3,5,0,5,5,2,7,1...$$
• restos modulo 9: $$0,1,1,2,3,5,8,4,3,7,1,8,0,8,8,7,6,4,1,5,6,2,8,1...$$

El período en función del divisor n se indica: $$\pi(n)$$ $$\pi(2)=3, \pi(3)=8,\pi(4)=6,\pi(5)=20$$ $$\pi(6)=24, \pi(7)=16, \pi(8)=12, \pi(9)=24$$ Conforme aumenta el valor del divisor, en general, tiende a aumentar el período. Salvo el caso de n=3 todos los períodos son un número par. Si dos números,m y n, son coprimos: $$\pi(m\cdot n)=\pi(m)\cdot\pi(n)\rightarrow \pi(3)\cdot\pi(4)=8\cdot 6=24=\pi(12)$$

Para las potencias de 2:

$$\pi(n)=\frac{3n}{2}\rightarrow \pi(2)=3, \pi(4)=6, \pi(8)=12$$

Para las potencias de 5:

$$\pi(n)=4n\rightarrow \pi(5)=20$$

Considerando la sucesión de restos módulo 3, dibujamos en un circulo tres puntos equdiastantes correspondientes a los tres restos posibles. Siguiendo la sucesión, se une con un segmento cada punto de un término con el punto del término siguiente (en el caso de coincidir dos términos consecutivos no se traza ningún segmento). En la imagen se muestra como se completa la figura.

En la imagen se muestran las figuras obtenidas para las sucesiones de módulo 2, 3,4,5,6,7,8 y 9.

Nos fijamos en el número de ceros que tiene cada ciclo: 2(1), 3(2), 4(1), 5(4), 6(2), 7(2), 8(2) y 9(2). Si tiene 1 cero hay asimetría, si tiene 4 ceros tiene simetría y si tiene 2 ceros puede o no tener simetría.
En el caso de módulo 10, el periodo es: $$\pi(10)=\pi(2)\cdot\pi(5)=3\cdot 20=60$$ y el ciclo tiene 4 ceros y por tanto la figura es es simétrica.

• Se puede ver la construcción 'paso a paso'.

Si nos fijamos en los términos de la sucesión de Fibonacci: ...8, 13, 21, 34, 55, 89,... las figuras obtenidas de los restos módulo 8, 21, 55 son idénticas y lo mismo ocurre con las figuras de los restos módulo 13, 34, 89.

Los números de Lah y de Hal

Los números de Lah fueron descubiertos, en 1954, por el matemático esloveno Ivo Lah (1896-1979)  y son los coeficientes que permiten expresar factoriales crecientes en función de factoriales decrecientes.

Un factorial creciente es:

$$x^{(n)}=x(x+1)(x+2) \cdots (x+n-1)$$

Un factorial decreciente es:

$$x_{(n)}=x(x-1)(x-2) \cdots (x-n+1)$$

Así, por ejemplo, se tiene que:

$$x^{(3)}=x(x+1)(x+2)=6x+6x(x-1)+1x(x-1)(x-2)$$

$$x^{(3)}=6x_{(1)}+6x_{(2)}+1x_{(3)}$$

Los números de Lah se denotan como L(n,k) donde n es el grado del polinomio creciente y k los grados de los polinomios decrecientes. Así, en el ejemplo, los números de Lah son:

$$L(3,1)=6, L(3,2)=6, L(3,3)=1$$

y por tanto:

$$x^{(3)}=L(3,1)x_{(1)}+L(3,2)x_{(2)}+L(3,3)x_{(3)}$$

La fórmula general para obtener los factoriales crecientes en función de los factoriales decrecientes es:

$$x^{(n)}=\sum_{k=1}^{n}L(n,k)x_{(k)}$$

y la fórmula para obtener los números de Lah directamente es:

$$L(n,k)=\left( \begin{array}{c} n-1\\ k-1 \end{array} \right) \frac{n!}{k!}$$

Hay una fórmula de recurrencia para obtener, a partir de L(n,1)=n!,  los demás términos del polinomio dado:

$$L(n,k+1)=\frac{n-k}{k(k+1)}L(n,k) \rightarrow L(3,2)=\frac{3-1}{1·2}L(3,1)=6$$

Hay otra fórmula de recurrencia para obtener nuevos números al variar n:

$$L(n+1,k)=(n+k)L(n,k)+L(n,k-1)$$

$$L(n,0)=0 \wedge L(n,k)=0 \wedge k>n$$

Por ejemplo, para obtener los números de Lah para el polinomio de cuarto grado a partir de los números del polinomio de grado tres:

$$L(4,1)=(3+1)L(3,1)+L(3,0)=4·6+0=24$$

$$L(4,2)=(3+2)L(3,2)+L(3,1)=5·6+6=36$$

$$L(4,1)=(3+3)L(3,3)+L(3,2)=6·1+6=12$$

$$L(4,1)=(3+4)L(3,4)+L(3,3)=4·0+1=1$$

Por otra parte llamaremos números de Hal a los coeficientes que permiten expresar factoriales decrecientes en función de factoriales crecientes.

$$x_3{(3)}=x(x-1)(x-2)=6x-6x(x+1)+1x(x+1)(x+2)$$

$$x_{(3)}=6x^{(1)}-6x^{(2)}+1x^{(3)}$$

Así, en el ejemplo, los números de Hal son:

$$H(3,1)=6, H(3,2)=-6, H(3,3)=1$$

y por tanto:

$$x_{(3)}=H(3,1)x^{(1)}+H(3,2)x^{(2)}+H(3,3)x^{(3)}$$

La fórmula de recurrencia es:

$$H(n+1,k)=(n+k)H(n,k)-H(n,k-1)$$

$$H(n,0)=0 \wedge H(n,k)=0 \wedge k>n$$

La fórmula cerrada es:

$$H(n,k)=(-1)^k \left( \begin{array}{c} n-1\\ k-1 \end{array} \right) \frac{n!}{k!}$$

El problema de la suma cuadrada

Elige un número entero N. Dados todos los números enteros de 1 a N, ¿se pueden ordenar de manera que cada par adyacente sume un número cuadrado? Empecemos con un conjunto pequeño de números no consecutivos, que se pueden ordenar para conseguir el objetivo: $$\{1,3,6,8,10\} \rightarrow \{8,1,3,6,10\}\rightarrow \{9,4,9,16\}=\{3^2,2^2,3^2,4^2\}$$

No hay forma de encontrar una solucíón sin probar todas las opciones. Es un problema de los llamados tipo NP-complejo. La mejor forma de visualizar estas relaciones es mediante un grafo donde los números son los vértices y las aristas conectan dos vértices cuya suma sea un número cuadrado. El problema tiene solución si hay un camino hamiltoniano, es decir, si podemos pasar una sola vez por todos los vértices.

Se observa que se pueden enlazar hasta 17 números, pero que al añadir el número 18 no es posible:

$$\{17,8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,16\}$$

$$\{25,9,16,25,16,9,16,25,16,9,16,25,16,9,16,25\}$$

Se puede ver la construcción 'paso a paso'.

Si añaden los números 19, 20, 21 y 22 sigue sin funcionar, pero si añade el número 23 si se consigue un camino hamiltoniano y por tanto hay una solución:

$$\{18,7,9,16,20,5,11,14,2,23,13,12,4,21,15,10,6,19,17,8,1,3,22\}$$

$$\{25,16,25,36,25,16,25,16,25,36,25,16,25,36,25,16,25,36,25,9,4,25\}$$

Si añadimos el número 24 vuelve a fallar pero desde el número 25 en adelante siempre hay una solución.

Los números de las mazmorras

En un castillo las torres están en la parte alta. De forma simbólica podemos considerar las potencias de potencias como las escaleras para alcanzar la torre. Las operaciones se pueden hacer de abajo a arriba (con paréntesis), o de arriba a abajo (lo correcto).

En el caso ascendente hemos obviado los paréntesis y el resultado, aunque grande, no es comparable con el obtenido en el caso descendente.

Un número  a en base b se obtiene de la siguiente manera:

$$a_b \rightarrow 123_4=(3·4^0+2·4^1+1·4^2)_{10}=27_{10}$$ Pero si hacemos una cadena de números de la forma: $$a_{b_c}$$ diremos, en forma simbólica, que las escaleras nos conducen a las mazmorras o calabozos. En imagen se muestra al amo del calabozo, personaje mítico del famoso juego de rol 'Dragones y Mazmorras'.

Veamos como se van obteniendo los diferentes resultados, a partir del número 10 e incrementando una unidad la nueva base, según se vayan realizando de abajo a arriba (lo correcto) o de arriba a abajo (con paréntesis).

Aunque parece que el orden no altera el resultado, no es cierto si seguimos avanzando en la serie. Cuando vamos de abajo a arriba se tiene:

$$10, 11, 13, 16, 20,25 , 31, 38, 46, 55, 65, 87, ...$$

En cambio si vamos de arriba a abajo los valores son:

$$10, 11, 13, 16,20,30,48,76,132,420,1640,11991...$$

y el crecimiento es mucho más rápido.

Si en vez de ir aumentando desde 10 de forma descendente, se hace de forma ascendente se obtiene:

Y en este supuesto, si vamos de abajo a arriba se tiene la serie: 

$$10, 11, 13, 16, 20,25 , 31, 38, 46, 55, 110,221, ...$$

En cambio, si vamos de arriba a abajo los valores son:

 $$10, 11, 13, 16, 20,28 , 45, 73, 133,348, 4943,22779, ...$$

y también el crecimiento es más rápido.

En particular, para n=35 se obtienen, respectivamente, los siguientes resultados: $$9153583, 8.6168...10^{643}, 41795936, 1.2327...10^{898}$$

Por tanto, cuando se desciende a las mazmorras del castillo, los números obtenidos, aún siendo grandes, no tienen comparación con los obtenidos cuando se sube a las torres del castillo.

Un número no entero en base b se obtiene de la siguiente forma:

$$123.45_b=1·b^2+2·b^1+3·b^0+\frac{4}{b}+\frac{5}{b^2}$$

Si lo aplicamos,de abajo a arriba, a una serie descendente con todos los valores iguales: $$a_{{a_{a}}_{...}}$$, para a=1.1 se obtienen los valores:

Si se obtienen más términos, se observa que la serie va a converger y por tanto, como la diferencia entre dos términos consecutivos será cada vez menor, se debe cumplir que:

 $$1+\frac{1}{\phi}=\phi \rightarrow \phi^2-\phi-1=0 \rightarrow \phi=\frac{1+\sqrt 5}{2}=1.6180...$$ que corresponde al número de oro.

Si a>10 diverge, si a=10 siempre es 10 pero si 1<a<10 es un sistema dinámico de manera que converge a un único valor (ej. a=1.1 al número de oro), bien oscila entre dos valores ( a=1.05) o diverge (ej. a=100/99).

Basado en el paper 'Descending Dungeons and Iterated Base-Changing' de David Applegate, Marc LeBrun and N. J. A. Sloane.

¡Adivina el cumpleaños! (II)

Vamos, de nuevo, a sorprender a nuestros amigos y amigas adivinando el día del cumpleaños.  Le pedimos a alguien que multiplique el día de su cumpleaños (D) por 12 y el mes (M) del mismo por 31, sume ambos valores y nos dé el resultado (N). Esto nos permitirá adivinar la fecha de su cumpleaños.

Se trata de resolver la ecuación diofántica:

$$N=12D+31M$$

Si la fecha es el 6 de Octubre, nos dará el número:

$$12·6+31·10=382=31·12+10$$

Cogemos el resto de la división del número entre 12 y lo multiplicamos por 7:

$$7·10=70=12·5+10$$

y el resto de la división de este número entre 12 nos da el mes:  Octubre.

Si en la ecuación inicial, hacemos M=10 se tiene el día del mes:

$$D=\frac{382-31·10}{12}=6$$

¿Qué ocurre si el cumpleaños es en el mes de Diciembre?

 Sea la fecha el 25 de Diciembre:

$$12·25+31·12=672=56·12$$

Se obtiene un múltiplo de 12 (la división entre 12 es exacta) y el mes es Diciembre.

El día se calcula de forma análoga:

$$D=\frac{672-31·12}{12}=25$$

EXPLICACIÓN:

$$N=12D+31M=12D+24M +7M=12(D+2M)+7M$$

y entonces  N y 7M tienen el mismo resto al dividir por 12.

Si multiplicamos ambos números por 7 se  obtienen 7N y 49M que seguirán teniendo el mismo resto al dividir por 12. Como:

$$49M=48M+M=12(4M)+M$$

y entonces 7N y M tendrán también el mismo resto al dividir por 12. Por tanto el resto de dividir 7N entre 12 será M. Pero como 7M es el primer resto, basta obtener el resto de 7·7M=49M para obtener el valor de M. Si el resto de 7M=0, eso significa que M=12 y el mes es Diciembre. Para calcular el día basta sustituir M en la ecuación:

$$D=\frac{N-31M}{12}$$

Hemos utilizado  la congruencia de números:

Se dice que a y b son congruentes módulo m si al dividir ambos números por m se obtiene el mismo resto y se expresa: $$a\equiv b\mod{12}$$.

Por tanto, las relaciones anteriores se pueden expresar de la forma:

$$N\equiv 7M\mod{12} \rightarrow 7N\equiv 49M\mod{12}$$

$$49M\equiv M\mod{12}$$

Veamos que la solución es única. Si hubiera dos soluciones se tendría:

$$N=12D_1+31M_1 \wedge N=12D_2+31M_2$$

y restando miembro a miembro:

$$12(D_1-D_2)+31(M_1-M_2)=0 $$

De donde se deduce que el número:

$$12(D_1-D_2)$$

debería ser un múltiplo de  31 pero como D1-D2 es necesariamente menor que  31, sólo podría dividirse por 31 cuando D1=D2, es decir si las soluciones coinciden y se llega a una contradicción (Demostración por "reducción al absurdo").

Problema de Josefo

Flavio Josefo (37-100) en su libro La Guerra de los judíos, nos dejó un interesante problema de matemáticas que ha tenido muchas variantes en los juegos de niños  y que ha atraído a muchos matemáticos. Cardano (1501-1576) recogió una versión del juego que llamó Ludus Josephi y fue Euler (107-1783) el primero que encontró leyes de recurrencia para resolver el problema.

Josefo pertenecía a la aristocracia sacerdotal de Jerusalén y en el año 63 fue enviado a Roma para conseguir la liberación de varios sacerdotes que habían sido hecho prisioneros y lo consiguió gracias a Popea, esposa de Nerón. A su vuelta a Jerusalén, en el año 65, la guerra  con Roma parecía inevitable, Josefo fue nombrado gobernador de Galilea, la guerra se desató al año siguiente y duró hasta el año 73.

 Cuenta Josefo, que cuando los romanos tomaron Jotapata, en la Baja Galilea, él y cuarenta galileos se refugiaron en una cueva y fueron cercados por los romanos. Decidieron morir antes que ser capturados y vendidos como esclavos. Para cumplir esa terrible decisión se colocarían en círculo con los lugares numerados y se matarían entre ellos con una espada mediante el siguiente procedimiento:

El primero mataría al segundo y pasaría la espada al tercero; éste mataría al cuarto y pasaría la espada al quinto y así sucesivamente hasta quedar uno que se quitaría así mismo la vida. Josefo, que sabía de matemáticas, se colocó en la posición del último superviviente y convenció al penúltimo superviviente para entregarse juntos a los romanos y evitar las dos muertes.

En la imagen vemos quién es el superviviente (en blanco) según haya 7 u 8 personas. En diferente color se muestran los eliminados en cada vuelta. Siempre es el 1 el que inicia el proceso.

En la tabla se muestra, para los 16 primeros casos, la posición del superviviente G(n) según el número n de participantes.

Se observa que cuando el número de participantes es una potencia de 2 siempre se salva el que empieza. Se puede comprobar siguiendo las ruedas de 8, 4, 2 y 1 que se muestran en la imagen:

Veamos como se puede obtener para n=13, de forma analítica, el valor G(13)=11:
$$13=8+4+1=8+5=2^3+5$$ $$n=13 \rightarrow G(n)=2·5+1=11$$ Si n es el número de individuos, k el exponente de la potencia de 2 más próxima a n y m lo que falta para ser n, se tiene: $$n=2^k+m \rightarrow G(n)=2m+1$$ En el caso histórico donde n=41 , se tiene: $$41=2^5+9\rightarrow G(41)=2·9+1=19$$ Si expresamos 13 en sistema binario: $$13=8+4+1=2^3+2^2+2^0=1101 $$ y pasamos la primera cifra a la última posición, se obtiene el número buscado: $$1011=2^3+2^1+2^0=8+2+1=11$$ En el caso histórico se tiene: $$41=32+8+1=2^5+2^3+2^0=101001 $$ y pasamos la primera cifra a la última posición, se obtiene el número buscado: $$010011=2^4+2^1+2^0=16+2+1=19$$

Aritmética Lunar (II)

En la Aritmética Lunar también se pueden construir cuadrados mágicos: la suma de cada fila, de cada columna y de las dos diagonales deben valer lo mismo.

El cuadrado mágico que se muestra es el más pequeño posible en cualquier base mayor que 2.

También se puede obtener un cuadrado mágico en base 2:

Un número lunar m se dice que domina a un número lunar n si los dígitos de m son mayores que los dígitos correspondientes de n. Esto es equivalente a que m+n=m. Por ejemplo 375 domina a 172. Si B es la base de numeración, se indica de la forma siguiente:

$$m \gg_B n, 375\gg_B 172 $$
En los dos cuadrados mágicos, se observa, que hay una entrada que domina a todas las demás (22 y 1111). Se observa que si una entrada domina a todas las demás, su valor debe coincidir con las sumas del cuadrado mágico.

¿Hay cuadrados mágicos en los que la entrada mayor no coincide con el valor de las sumas?. La respuesta es sí y se muestra en el cuadrado mágico de la izquierda donde la mayor entrada es 43 y las sumas son 44.

Además como en la suma de la la Aritmética Lunar no hay 'acarreos', cualquier cuadrado formado por un subconjunto de dígitos de un cuadrado mágico también lo es, como se observa en el cuadrado mágico de la derecha formado únicamente por las decenas del anterior.

Por tanto, cualquier cuadrado mágico se puede representar como suma de cuadrados mágicos como se muestra a continuación.

Los dos primeros cuadrados mágicos representan los únicos casos de entradas mínimas usando un único dígito (no se consideran las rotaciones y reflexiones). El de la derecha no se considera como tal pues si se elimina una entrada (poner 0) sigue siendo mágico, cosa que no ocurre con los otros dos.

También se pueden formar cuadrados mágicos de potencias. El cuadrado mágico de la derecha parece ser el más pequeño posible. El primero tiene como sumas 48·48=448 y el segundo 24·24=224, es decir, que las sumas  en ambos cuadrados mágicos son también potencia de 2.

Si un número a tiene las cifras  en orden creciente de izquierda a derecha: $$a=a_k\dots_1a_0 \wedge a_{i+1} \leq a_i$$ entonces la potencia de orden n del número a se obtiene repitiendo n veces cada cifra excepto la última: $$a^n=\overbrace{a_ka_k\dots a_k} \dots \overbrace{a_1 a_1\dots a_1}a_0$$ En el cuadrado mágico siguiente se ha aplicado este método para la tercera potencia:

Vemos que la potencia obtenida es también un cuadrado mágico. Cualquier potencia dará un cuadrado mágico y por tanto existirán infinitos cuadrados mágicos de esas potencias. Existen otras familias de potencias como la que se muestra a continuación:

El siguiente es un cuadrado mágico de cuadrados en base 2. Su sumas son 1001·1001 y es el más pequeño posible en dicha base:

El siguiente cuadrado mágico de cuadrados no da una suma que sea a su vez un cuadrado, como en los casos anteriores. Las sumas valen 439 que además es un número primo lunar.

Existen cuadrados mágicos de cuadrados cuya suma es también un cuadrado mágico de cuadrados. Forman tripletas pitagóricas y en estos cuadrados se muestran nueve. Cumplen el Teorema de Pitágoras en la Aritmética Lunar.