Mostrando entradas con la etiqueta matemática discreta. Mostrar todas las entradas
Mostrando entradas con la etiqueta matemática discreta. Mostrar todas las entradas

viernes, 11 de septiembre de 2026

Modelo Friekin-Johnsen

El modelo de Friedkin-Johnsen (FJ) es un marco matemático que explica cómo se forman las opiniones en grupos sociales, destacando que las personas no solo se dejan influir por otros, sino que mantienen una resistencia o ‘terquedad’ basada en sus creencias iniciales. El modelo FJ muestra cómo la resistencia a cambiar de opinión (terquedad) mantiene la polarización y el desacuerdo incluso tras largas interacciones. Se utiliza para diseñar algoritmos que intenten reducir este conflicto social. Para entender el modelo de Friedkin-Johnsen (FJ), imagina que cada persona tiene una opinión inicial (su ‘prejuicio’ o valor innato) que nunca cambia del todo, a pesar de lo que digan los demás. La fórmula de actualización es: $$X_i(t+1)=\lambda_i( \sum_{j=1}^n w_{ij}\cdot X_j(t))+(1-\lambda_i) \cdot S_i$$ $$S_i, \ \lambda_i, \ w_{ij} $$ son tu opinión personal (fija), tu susceptibilidad (cuanto te dejas influir), y la confianza que tienes de la opinión de la persona j. La fórmula siguiente representa la influencia de la red en cada etapa. $$ \sum_{j=1}^n w_{ij}\cdot X_j(t)$$
Supongamos dos agentes A y B con opiniones opuestas sobre un tema concreto: A está muy a favor S1=1 y B está muy rn contra S2=0; suponemos que las susceptibilidades son 0.5, y 0.4 respectivamente. Por último el agente A escucha 0.4 al agente B , en cambio el agente B escucha 0.8 al agente A. Al final las opiniones se acercan, aunque no llegan a un consenso, como se observa en la gráfica.


Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
  • Puedes modificar la susceptibilidad de cada agente.
  • Puedes modificar la confianza o escucha de cada agente.
  • Puedes modificar el instante del proceso y observar los valores de cada agente en ese momento.
Descargar .XLS




domingo, 2 de agosto de 2026

Teorema del alpinismo

El problema del alpinismo es un problema matemático que considera una cordillera bidimensional (representada como una función continua) y plantea la cuestión de si es posible que dos alpinistas, partiendo desde el nivel del mar en los flancos izquierdo y derecho de la montaña, se encuentren en la cima, manteniendo la misma altitud en todo momento. Se ha demostrado que cuando la cordillera tiene un número finito de picos y valles, siempre es posible coordinar los movimientos de los alpinistas, pero esto no se cumple necesariamente cuando tiene un número infinito de picos y valles.


Este problema fue nombrado y planteado de esta forma por James V. Whittaker (1966), pero su historia se remonta a Tatsuo Homma (1952), quien resolvió una versión del mismo.
Sea una cordillera con tres picos y dos valles. Se trazan líneas horizontales por cada pico o valle. Cada escalador parte desde el mar en las posiciones 0. El escalador rojo se mueve por la parte izquierda en el intervalo [0,1] y el escaldor azul se mueve por la parte derecha en el intervalo [1,0].

.Así el rojo  está en la posición 2/7 y el verde en la posición 6/7. Al estar el rojo en un pico, el azul puede estar en alguna de las tres posiciones. Los estados vienen dados por el par formado por las posiciones de los escaladores; así la posición de la figura es (2/7,6/7), pero podrían ser los estados (2/7,4/7) y (2/7,2/7). Si el azul baja al valle, el rojo tiene dos opciones como se muestra con trazo grueso.

El ascenso correcto es: el escalador rojo sube al  pico (1), luego baja al valle (2), el escalador azul sube al pico (3), luego baja al valle (4) y finalmente ambos, llegan a la cumbre (5).

¿Por qué esa es la ruta correcta?

Para ello establecemos un grafo donde los vértices son los estados posibles y las aristas conectan el paso de un estado a otro. Entonces el camino (línea discontinua) que va desde el vértice de salida (0,0) y termina en el vértice de llegada (1,1) es la ruta correcta. Con trazo rojo se muestran las alternativas del vértice rojo de la figura anterior. Además  hay dos estados por los que no se pasa (línea continua).
Las decisiones a tomar según la posición en que se encuentren los escaladores pueden ser:
  • En el vértice (0, 0), el grado es uno: la única dirección posible para ambos escaladores es hacia la montaña. De manera similar, en el  vértice (1, 1)  el grado es uno, ya que ambos escaladores solo pueden regresar montaña abajo.
  • En un vértice donde un escalador se encuentra en una cima o un valle y el otro no, el grado es dos: el escalador en la cima o el valle tiene dos opciones sobre qué camino tomar, y el otro escalador solo puede ir por un camino.
  • En un vértice donde ambos escaladores se encuentran en una cima o en un valle, el grado es cuatro: ambos escaladores pueden elegir independientemente el uno del otro en qué dirección ir.
  • En un vértice donde un escalador se encuentra en una cima y el otro en un valle, el grado es cero: dichas posiciones son inalcanzables. (es decir, si existe tal vértice, entonces el grafo no es conexo).
  • Según el 'lema del apretón de manos': la suma de los grados de todos los vértices de un grafo conexo es siempre un número par, lo que significa que el número de personas que saludan un número impar de veces debe ser par (hay un número par de vértices de grado impar).
  • Dado que los únicos vértices de grado impar son (0,0) y (1,1), estos dos vértices deben pertenecer a la misma componente conexa. Es decir, el grafo debe contener un camino desde (0,0) hasta (1,1). Este camino indica cómo coordinar el movimiento de los escaladores hacia la cima.

viernes, 30 de enero de 2026

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.


sábado, 27 de diciembre de 2025

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.










viernes, 6 de diciembre de 2024

Sucesión de Connell

La sucesión de Connell es una sucesión de números naturales construida de la siguiente manera: empezamos anotando el primer impar, luego los dos siguientes pares, los tres siguientes impares,…. Y así, sucesivamente, formando la sucesión: $$1, 2, 4, 5, 7, 9, 10, 12, 14, 16, \dots$$ El término general de esta sucesión viene dado por la expresión: $$C_n=2n-\lfloor \frac{1}{2} \sqrt{8n+7}+1\rfloor$$ Para términos, suficientemente avanzados, se cumple: $$ \lim \limits _{n \rightarrow \infty} \frac{C_n}{n}=2$$ Las subsucesiones son: $$ S_1=\{1\}, S_2=\{2,4\}, S_3=\{5,7,9\}, S_4=\{10,12,14,16\} \dots$$ Los números triangulares (poligonales de orden 3) se obtienen con la fórmula: $$T(n)=P_3(n)=\frac{1}{2}n(n+1) \rightarrow 1, 3, 6, 10, ...\dots$$ Observando los últimos números de cada subsucesión se cumple: $$C(T_n)=n^2$$ Stevens generalizó la sucesión de Connell, donde el término general es: $$C_{m,r} \wedge m \geq 2 \wedge r \geq 1$$ Se parte del entero 1 que es un número congruente con 1 (mod m); le sigue el entero 1+r congruente con 2 (mod m); luego el entero 1+2r congruente con 3 (mod m) y así sucesivamente. Si m=2 y r=1 (los valores mínimos) se obtiene la sucesión de Connell. De forma más detallada se tiene su definición:
  • La sucesión está formada por subsucesiones concatendas S1, S2, S3,...
  • La subsucesión S1 está formada por el elemento 1.
  • Si la subsucesión Sn termina en el elemento e, la subsucesión Sn+1 empieza en e+1.
  • Si la subsucesión Sn contiene t términos, la subsucesión Sn+1 contiene t+r términos.
  • Si la sucesión es creciente y la diferencia entre dos términos consecutivos de la misma subsucesión es m.
Sea la sucesión: C3,2: 1;2,5,8;9,12,15,18,21;22,25,28,31,34,37,40,...

Los números octogonales (poligonales de orden 8) se obtienen con la fórmula: $$P_8(n)=n(3n-2) \rightarrow 1, 8, 21, 40, ...\dots$$ Observando los últimos números de cada subsucesión se cumple: $$P_8(n)=C_{3,2}(n^2)$$ Sea la sucesión: C3,1: 1;2,5;6,9,12;13,16,19,22;23,26,29,32,35...

Los números pentagonales (poligonal de orden 5) se obtienen con la fórmula: $$P_5(n)=\frac{1}{2}n(3n-1) \rightarrow 1, 5, 12, 22, 35...\dots$$ Se observa que los últimos números de cada subsucesión son P5(n).

Hay una fórmula general para los números poligonales: $$P_k(n)=\frac{1}{2}n[(k-2)n-k+4]$$ que se puede comprobar su validez para los casos anteriores y obtener P4(n): $$P_3(n), P_5(n), P_8(n), P_4(n)=n^2$$. También existe otra fórmula general que relaciona las sucesiones generalizadas de Connell con los número poligonales: $$C_{m,r}[P_{r+2}(n)]=P_{m\cdot r+2}(n)$$ que se puede aplicar a dos casos anteriores: $$C_{2,1}[P_3(n)]=P_4(n) \wedge C_{3,2}[P_4(n)]=P_8(n)$$ Para términos suficientemente avanzados, se cumple: $$ \lim \limits _{n \rightarrow \infty} \frac{C_{m,r}(n)}{n}=m$$

jueves, 30 de noviembre de 2023

Dados no transitivos (III)

Se pueden construir dados no transitivos utilizando los sólidos platónicos. El hexaedro o cubo está representado por el 'Efron Dice'. Para el tetraedro se tiene el 'Tiggermann Dice' que se muestra en la figura.
Se puede extender el 'Tiggermann Dice' para el tetraedro al octaedro, simplemente repitiendo los valores de las caras: $$1,1,4,4,4,4,4,4$$ $$3,3,3,3,3,3,6,6$$ $$2,2,2,2,5,5,5,5$$ Nicholas Pasciuto propone otra numeración de las caras y le llama 'Nichlman Dice' formado por las primeras letras de su nombre y las últimas del apellido de su mentor el Dr. Ward Heilman.
Para el dodecaedro existen varios conjuntos de dados. Uno de ellos es ampliar para cuatro caras más 'Timmermann Dice'. Otra opción es el conjunto de dados 'Schward Dice'
$$0,0,0,0,0,16,16,17,17,17,17,17$$ $$5,5,5,5,14,14,14,14,18,18,18,18$$ $$6,6,6,12,12,12,19,1,9,19,19,19,19$$ $$3,3,11,11,11,11,11,20,20,20,20,20$$ $$15,15,15,15,15,15,15,15,15,15,15,15$$ 
Michael Winkleman inventó un nuevo conjunto no transitivo de sólo tres dados que llamó 'Miwin's Dodecahedral Dice'.
Finalmente para el icosadero se puede expandir el 'Timmermann Dice'. Otra posibilidad, no reversible con dos dados, es el conjunto 'Pascanell Dice'.

miércoles, 19 de abril de 2023

Dados no transitivos (I)

Sean tres dados: rojo, verde y azul con sus caras numeradas como se muestra en la imagen.
Si el primer jugador elige el dado verde, entonces, si el segundo jugador elige el dado rojo tiene una mayor probabilidad de ganar. Observando el diagrama de árbol:
$$p(R>V)=p(3)·p(2)+p(6)=\frac{5}{6}·\frac{1}{2}+\frac{1}{6}=\frac{7}{12}$$ Análogamente el dado verde 'gana' al azul y el dado azul 'gana' al rojo: $$p(V>A)=p(2)·p(1)+p(5)=\frac{1}{2}·\frac{1}{6}+\frac{1}{2}=\frac{7}{12}$$ $$p(A>R)=p(4)·p(3)=\frac{5}{6}·\frac{5}{6}=\frac{25}{36}$$
Se forma un ciclo que se visualiza en el grafo dirigido de la imagen y por tanto no se cumple la propiedad transitiva. Por lo tanto, siempre que tu oponente elija primero, siempre podrás elegir un dado con más posibilidades de ganar, con una probabilidad promedio de ganar de alrededor del 62%, aunque te gustaría que eligiera el dado rojo.
Tim Rowett presentó este juego de dados no transitivos en el Gathering for Gardner V (2002). Es una fundación educativa sin ánimo de lucro para mantener el legado del divulgador matemático Martin Gardner (1914-2010).

Si se lanzan dos dados del mismo color entonces el ciclo se invierte. Los dados verdes 'ganan' a los dados rojos: $$ p(VV>RR)=p(7)·p(6)+p(10)·p(6)+p(10)·p(9)=$$ $$\frac{18}{36}·\frac{25}{36}+\frac{9}{36}·\frac{25}{36}+\frac{9}{36}·\frac{10}{36}=\frac{765}{1296}=\frac{85}{144}$$ teniendo en cuenta que los dados verdes pueden sumar 4,7,10 y los dados rojos pueden sumar 6,9,12.
En el diagrama de árbol se muestra como ganan los dados verdes a los dados rojos y el grafo dirigido visualiza un ciclo de sentido inverso.

Los dados azules 'ganan' a los dados verdes: $$ p(AA>VV)=p(5)·p(4)+p(8)·p(4)+p(8)·p(7)=$$ $$\frac{10}{36}·\frac{9}{36}+\frac{25}{36}·\frac{9}{36}+\frac{25}{36}·\frac{18}{36}=\frac{765}{1296}=\frac{85}{144}$$ teniendo en cuenta que los dados azules pueden sumar 2,5,8 y los dados verdes pueden sumar 4,7,10.

Los dados rojos 'ganan' a los dados azules: $$ p(RR>AA)=p(6)·p(2)+p(6)·p(5)+p(9)+p(12)=$$ $$\frac{25}{36}·\frac{1}{36}+\frac{25}{36}·\frac{10}{36}+\frac{10}+\frac{1}{36}=\frac{671}{1296}$$ teniendo en cuenta que los dados rojos pueden sumar 6,9,12 y los dados azules pueden sumar 2,5,8. La probabilidad media de ganar con dos dados es alrededor del 57% y la probabilidad de que los dados rojos ganen a los dados azules es muy ajustada.
Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
  • Se puede jugar contra el ordenador eligiendo el número de partidas y en cada tirada cualquiera de los tres colores con los botones de la izquierda.
  • Se muestran los resultados acumulados después de cada tirada así como la gráfica correspondiente.
  • Se puede jugar contra el ordenador eligiendo series de jugadas del tamaño deseado y siempre con un color determinado con los botones de la derecha.
  • Se muestran los resultados acumulados después de cada serie así como la gráfica correspondiente.
Descargar .XLS

lunes, 29 de agosto de 2022

Modelos de urnas

Un modelo de urnas se construye a partir de un conjunto de urnas que contengan bolas de diferentes colores. Luego se establecen unas reglas que fijan el procedimiento de añadir o retirar bolas de las urnas en función del color de la bola extraída.  Dentro de los modelos de urnas tienen una importancia especial los llamados "Modelos por Contagio", esto es, modelos donde la ocurrencia de un suceso tiene efecto de cambiar la probabilidad de las posteriores ocurrencias de ese mismo suceso. 

Una urna contiene N bolas, a rojas y b verdes; se extrae al azar una bola, se reemplaza y se añaden c bolas del mismo color y d bolas del color contrario. Se hace una nueva extracción aleatoria de la urna (que ahora contiene a+b+c+d bolas) y se repite el procedimiento sucesivamente. 

Modelo directo:

Cuando se fija el número n de repeticiones del experimento y se conoce como el  Modelo de Bernard Frieman que lo propuso en 1947. Viene definido por los siguientes parámetros:
$$(a,b,c,d,n)$$
El Modelo de Pólya es un caso particular del modelo anterior cuando el parámetro d=0, y viene definido por los parámetros:
$$(a,b,c,0,n)$$
La probabilidad de que la primera bola extraída sea roja es:
$$p(r_1)=\frac{a}{N}$$
La probabilidad de que las dos primera bolas extraídas sean rojas es:
$$p(r_1,r_2)=\frac{a}{N}\frac{a+c}{N+c}$$
 La }de que las tres primera bolas extraídas sean rojas es:
$$p(r_1,r_2,r_3)=\frac{a}{N}\frac{a+c}{N+c}\frac{a+2c}{N+2c}$$
 La probabilidad de que las k primeras bolas extraídas sean rojas es:
$$p(r_1,r_2,\dots r_k)=\frac{a}{N}\frac{a+c}{N+c}\dots\frac{a+(k-1)c}{N+(k-1)c}=\frac{a^{(k,c)}}{N^{(k,c)}}$$
que es la forma simbólica y abreviada de expresar el productorio.
Si además se quiere que en las  restantes extracciones las bolas sean verdes:
$$p(r_1,r_2,\dots r_k,v_{k+1},v_{k+2}\dots v_n)=$$
$$\frac{a^{(k,c)}}{N^{(k,c)}}\frac{N-a}{N+kc}\frac{N-a+c}{N+(k+1)c}\dots \frac{N-a+(n-k-1)c}{N+(n-1)c}=$$
$$\frac{a^{(k,c)}(N-a)^{(n-k,c)}}{N^{(n,c)}}$$
Como esta probabilidad no depende del orden en que aparecen las k bolas rojas y las n-k bolas verdes, la fórmula final será:
$$\binom{n}{k}\frac{a^{(k,c)}(N-a)^{(n-k,c)}}{N^{(n,c)}}$$
Dependiendo del valor del parámetro c se tiene:
  • Si c>0 el éxito y el fracaso son contagiosos, en el sentido de que un éxito o un fracaso aumenta la probabilidad de un futuro éxito o fracaso, respectivamente.
  • Si c=0 los sucesos son independientes y no se alteran las condiciones iniciales.
  • Si c<0 el éxito disminuye la probabilidad de un nuevo éxito  y el fracaso disminuye la probabilidad de un nuevo fracaso.
Las distribuciones de probabilidad que obtienen según los valores del parámetro c son:
  • Si c=-1: Distribución hipergeométrica.
  • Si c=0: Distribución binomial.
  • Si c=1: Distribución hipergeométrica negativa.
  • Si c=a=N-a: Distribución uniforme discreta.
Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
  • Se puede elegir elegir el número de bolas negras 'N' y bolas rojas 'R' iniciales.
  • Se pueden modificar los parámetros 'a' y 'b' de bolas de cada color que se añaden en cada iteración.
  • Se puede fijar el número de iteraciones 'k'.
  • Se muestran los valores y la gráfica de las sucesivas iteraciones. 
  • Se muestran el número de bolas negras y rojas finales y su proporción.
Descargar .XLS

viernes, 21 de enero de 2022

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.

lunes, 27 de septiembre de 2021

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!}$$

lunes, 2 de agosto de 2021

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.

    miércoles, 19 de mayo de 2021

    Sucesiones de Fibonacci (III)

    Vimos una variante de la sucesión de Fibonacci que se obtenía sumando (o restando) a un término el anterior de forma aleatoria con probabilidad 1/2: cara (+) o cruz (-). La fórmula de recurrencia era: $$R_{n}=R_{n-1} \pm R_{n-2}$$ Si la secuencia aleatoria fuera: $$+,+,-,-,+,+,-,+,-,-,...$$ la sucesión sería: $$1,1,2,3,1,-2,-1,-3,-2,-5,-3,2,...$$ Ahora vamos a considerar series no aleatorias y repetidas de + y -, es decir, con un patrón fijo. Un ciclo de longitud n es: $$\sigma_n=(s_1,s_2,...,s_n) \wedge s_i\in\{+,-\} \wedge 1 \leq i \leq n$$ $$-,-,+,-,-,+,-,-,+,... \rightarrow 1,1,0,-1,-1,4,5,1,6,7,1,...$$ $$+,+,-,+,+,-,+,+,-,... \rightarrow 1,1,2,3,1,4,5,1,6,7,1,...$$ corresponde a los ciclos: $$ \sigma_3=(-,-,+) \wedge \sigma_3=(+,+,-)$$ Los resultados son muy diferentes dependiendo de la situación de esos símbolos en la cadena y de la longitud de la cadena de + y - . Si el ciclo tiene longitud n, el número de posibilidades es VR2,n.
    Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
    • Se puede obtener el valor de los los términos de la sucesión.
    • Se pueden analizar las series con ciclos de 2, 3, 4 y 5 elementos.
    • Se pueden modificar los signosn + y - de las series con ciclos de 2, 3, 4 y 5 elementos.
    • Se muestran las gráficas de los términos de la sucesión.
    Descargar .XLS

    viernes, 16 de abril de 2021

    Sucesiones de Fibonacci (II)

    Vamos a volver sobre la sucesión de Fibonacci: $$1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...$$ $$F_1=1,\quad F_2=1,\quad F_n=F_{n-1}+F_{n-2}$$ donde el cociente de dos términos consecutivos tiende al número de oro: $$\lim_{n \rightarrow \infty} \frac{F_{n+1}}{F_n}= \phi$$ Esto permite obtener de forma aproximada un término muy avanzado de la sucesión. $$F_n \approx F_{n-1} \cdot\phi \rightarrow F_n \approx F_{n-2} \cdot\phi^2 \rightarrow F_n \approx \cdot\phi^n $$ Si se quiere obtener un término conociendo el anterior, basta multiplicarlo por el número de oro y redondear: $$F_6 \approx F_5\cdot 1.61803...\approx 8.09016... \rightarrow F_6=8$$ Veamos la diferencia entre la aproximación y el verdadero valor del término 1000000: $$F_{1000000} \approx\phi^{1000000} \approx 4.4 \cdot 10^{208987}$$ $$F_{1000000}= 1.95 \cdot 10^{208987}$$ Supongamos ahora que la sucesión se obtiene sumando (o restando) a un término el anterior de forma aleatoria con probabilidad 1/2: cara (+) o cruz (-). La fórmula de recurrencia ahora será: $$R_{n}=R_{n-1} \pm R_{n-2}$$ Si la secuencia aleatoria fuera: $$+,+,-,-,+,+,-,+,-,-,...$$ la sucesión sería: $$1,1,2,3,1,-2,-1,-3,-2,-5,-3,2,...$$ ¿Tenderá a más infinito, a menos infinito, a cero o será caótica? Pues así como la sucesión de Fibonacci clásica tiende a una tasa de crecimiento, que es el número de oro, la sucesión de Fibonacci aleatoria también tiende a una tasa de crecimiento: $$1.1319882487943...$$ conocida como la constante de Wiswanath. Así que: $$R_{1000000}=1.1319882487943...^{1000000} \approx \pm 8.3 \cdot 10^{53841}$$ Otra forma de obtener la constante es: $$|R_n|^{\frac{1}{n}} \rightarrow 1.13198... \wedge n\rightarrow \infty$$ Es 'casi seguro', pues existe una remota posibilidad de obtener de forma aleatoria la sucesión de Fibonacci cuya ratio tiende al número de oro. Es evidente que, siguiendo el mismo procedimiento, se puede obtener 'seguro' el número de oro: $$|F_n|^{\frac{1}{n}} \rightarrow 1.61803... \wedge n\rightarrow \infty$$ Se puede considerar que sumar o restar no sea equiprobable y tenga un sesgo. Si la probabilidad de sumar es 1, se obtendrá la sucesión de Fibonacci clásica y si la probabilidad de restar es 1, entonces se obtiene la sucesión de Fibonacci oscilante con signos alternos. ¿Qué ocurre si sólo se le suma (resta) a un término la mitad del anterior? $$R_n=R_{n-1} \pm \frac{1}{2}R_{n-2}$$ Se obtiene una sucesión que tiende a cero. Pero para valores comprendidos entre 1/2 y 1 ni se anula ni tiende a infinito. Concretamente para el valor 0.70258... ni crece ni decrece. Esto significa que la tasa de crecimiento tiende, aproximadamente, a 1.
    Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
    • Se puede obtener el valor de los los términos de la sucesión.
    • Se puede obtener el valor absoluto de los los términos de la sucesión.
    • Se puede obtener el valor de la tasa de crecimiento.
    • Se puede elegir la probabilidad (m) de sumar o restar los términos.
    • Se puede elegir la proporción (s) del término que se suma o resta.
    • Se muestran las gráficas de los términos, los valores absolutos de los términos y los valores de la constante de Wiswanath.
    Descargar .XLS

    domingo, 21 de febrero de 2021

    Conjetura de Kollatz (II)

     La conjetura de Collatz, también conocida como la conjetura de 3n+1, conjetura de Ulam o problema de Siracusa, es una conjetura de la teoría de números establecida por Lothar Collatz en 1937.

    Si un número n es par se divide por 2:

    $$f(n)=\frac{n}{2}$$

    Si un número n es impar se multiplica por 3 y se le suma 1:

    $$f(n)=3n+1$$

    La conjetura dice: Si partimos de cualquier número natural y se aplican los criterios anteriores de  forma sucesiva a los números que se van obteniendo, siempre se termina en 1. Si se continuara el proceso se obtendría {4,2,1} de manera cíclica.

    Aunque no existe una demostración matemática de la conjetura, se ha probado que para números menores que 2^68 se cumple. Por otro lado, de los 100.000.000 primeros números, el que genera la secuencia más larga es el 63.728.127 que necesita 947 iteraciones.

    Los números que son suma de potencias de 2 con exponente par necesitan pocas iteraciones para llegar al 1. Por ejemplo:

    $$2^0+2^2=1+4=5\rightarrow 5·3+1=16=2^4$$

    $$2^0+2^2+2^4=1+4+16=21\rightarrow 21·3+1=64=2^6$$

    $$2^0+2^2+2^4+2^6=1+4+16+64=85\rightarrow 85·3+1=256=2^8$$

    Y como se llega a una potencia de 2, a partir de ahí sólo se necesitan  4, 6 y 8 iteraciones respectivamente.

    Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
    • Se puede elegir el valor inicial de la serie.
    • Se puede ir cambiando de iteración y obtener el valor correspondiente.
    Descargar .XLS

    domingo, 4 de octubre de 2020

    Superpermutaciones

    El 16 de septiembre de 2011, un aficionado al anime subió al foro de Internet 4chan una pregunta de matemáticas relativa a la serie de televisión de culto 'La melancolía de Haruhi Suzumiya'. La primera temporada de la serie, en la que hay viajes por el tiempo, no se emitió originalmente en orden cronológico; una emisión posterior y una versión en DVD reordenaron los episodios.

    Los seguidores de la serie debatieron en Internet acerca de cuál era el mejor orden de los episodios; el mensaje colgado en 4chan se preguntaba lo siguiente: si los espectadores quisiesen ver la serie ordenada de todas las maneras posibles, ¿cuál sería la lista con menos episodios que tendrían que ver?

    En menos de una hora, alguien, de forma anónima, ofreció una respuesta. No se trataba de una solución completa, sino de una cota inferior del número de episodios requerido. El argumento, válido para series con cualquier número de episodios, mostraba que para los 14 de la primera temporada de Haruhi los espectadores tendrían que ver al menos 93.844.313.611 episodios para que no se les escapase ninguna ordenación. 

    ¡Es el origen de las superpermutaciones!

    Una superpermutación es una cadena formada a partir de n símbolos de manera que las n! permutaciones de esos símbolos aparecen al menos una vez formando un bloque continuo de n caracteres en la cadena. Por ejemplo, con dos caracteres se tiene la superpermutación:

    $$ABA$$

    donde están las permutaciones AB y BA. 
    Dada una superpermutación de orden n-1, para obtener una superpermutación de orden n sigue los pasos del siguiente algoritmo:
    • Escribe las permutaciones de la última superpermutación en el orden en que aparecen.
    • Duplica cada una de ellas y coloca entre ellas el nuevo elemento.
    • Comprime el resultado utilizando todos los solapamientos posibles.

    $$A$$

    $$ABA$$

    $$AB \vert BA$$

    $$ABCAB \vert BACBA$$

    $$ABCABACBA$$

    $$ABC \vert BCA \vert CAB \vert BAC \vert ACB \vert CBA$$

    $$ABCDABC \vert BCADBCA \vert CABDCAB\vert$$

    $$\vert BAC DBAC\vert ACBDACB\vert CBADCBA$$

    $$ABCDABCADBCABDCABACDBACBDACBADCBA$$

    Vemos que las longitudes de las superpermutaciones son: L(1)=1, L(2)=3, L(3)=9 y L(4)=33. Siguiendo el proceso se obtendría L(5)=153. Cumplen la ecuación recursiva:

    $$L(n)=L(n-1)+n! \rightarrow L(n)=1!+2!+3!+ \dots +n!$$

    Para n=1,2,3,4 se obtienen las superpermutaciones más cortas y que son únicas.

    ¿Existe superpermutaciones de menor longitud que las que se obtienen de la fórmula anterior para cualquier valor de n?;

    En 2013, Nathaniel Johnston demostró que para n>=5 las soluciones obtenidas por el algoritmo podían no ser únicas. En 2014, Ben Chafin demostró que para n=5 aunque no había superpermutaciones más cortas había 8 diferentes. Poco después Robin Houston encontro una superpermutación para n=6 con 872 caracteres, una menos que L(6)=873. En 2013 Aaron Williams propuso la fórmula:

    $$L_2(n)=n!+(n-1)!+(n-2)! +(n-3)! +n-3$$

    Sólo funciona para n>3 y para n<6 genera cadenas más largas que el algoritmo estándar: L2(4)=34, L2(5)=154. Ya L(6)=L2(6) pero a partir de ahí el método es cada vez más eficiente.

    L2(7)=5908, 5 menos que L(7)=5915; L2(8)=46205, 28 menos que L(8)=46233; L2(9)=408966, 28 menos que L(9)=409113. En general:

    $$L_2(n)-L(n)=n-3-L(n-4)$$

    Sea un grafo dirigido donde los vértices son las diferentes permutaciones y las aristas tienen un peso que corresponde al número de elementos que hay que eliminar de una  permutación para obtener la siguiente. Por ejemplo, el paso de ABC a BCA supone quitar la A para ponerla al final. En cambio el paso de CAB a BAC supone quitar CA para ponerlo al final.

    En el problema de las superpermutaciones queremos dar con la secuencia más corta posible de dígitos que sea una lista de todas las permutaciones, así que el objetivo consiste en 'viajar' a través de todas las permutaciones con el menor coste posible. Establecemos que el coste de cada arista es  el número de dígitos que tenemos que añadir al final de una permutación para obtener la siguiente. Houston lo convierte en el Problema del Viajante y mediante este algoritmo consigue superpermutaciones de n caracteres de longitud menor que L(n).

    jueves, 13 de agosto de 2020

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

    jueves, 16 de enero de 2020

    Matemagia (II)

    Vamos a mostrar dos propuestas mágicas basados en los números primos.
    • PROPUESTA I: En una mesa coloca en círculo y boca abajo, 13 cartas. Elige una de ellas y la vuelves a poner boca abajo. A partir de esa carta y en el sentido de las agujas del reloj cuenta hasta llegar a la carta 8 y la volteas. A partir de esa carta repite el proceso volteando las cartas, sucesivamente, hasta que falte una que será la que has elegido. No importa al contar que estén del anverso o del reverso.

    ¡Los dos números han de ser primos entre sí: mcd(13,8)=1!

    EXPLICACIÓN:
    Sea n es el número de cartas en círculo y p el número pensado para contar con la condición de que mcd(n,p)=1. Podemos suponer, sin pérdida de generalidad, que la  carta elegida está en posición 0.  A partir de la siguiente, contamos p cartas y se voltea. A partir de ella se cuentan otras p cartas (hemos contado ya 2p) y se voltea. Así sucesivamente 3p, 4p,...Sólo cuando contemos n veces, np será múltiplo de n y sólo quedará sin voltear la carta buscada.
    Vamos a simplificarlo a 5 cartas {A,B,C,D,E} colocadas alfabéticamente en el sentido de la agujas del reloj, como se muestra en la figura. Si eliges la carta C (en naranja) y cuentas cada vez 3, se observa que la primera carta en voltear es la A (pasa de gris a blanco).  Y así sucesivamente se volteando las cartas D, B, E. Finalmente queda sin descubrir la carta C.
    Al hacer un recuento en círculo es un problema de congruencia módulo 5:
    3 mod 5=3 (A), 6 mod 5=1 (D), 9 mod 5=4 (B), 12 mod 5=2 (D), 15 mod 5=0 (C)

    • PROPUESTA II: Tomamos un número de tres cifras diferentes abc. A partir de él formamos el número de seis dígitos abcabc. Si se divide por 13, el resultado entero es divisible por 11 y al dividir el resultado por 7 se obtiene el número inicial. Sea el número 739739, al dividir por 13 se obtiene 56903. Al dividir ahora por 11 se obtiene 5173. Si finalmente se divide por 7 se obtiene 739.
    ¡Con números de esa forma ocurre siempre!

    EXPLICACIÓN:
    • Un número es divisible por 13 cuando la suma de los productos de las unidades, decenas, centenas... de dicho número por los dígitos de la lista {1,-3,-4.-1,3,4} respectivamente es  0 ó múltiplo de 13. No es el único criterio de divisibilidad.
    El número 53927 no es divisible y no se utilizan todos los dígitos de la lista: $$7·1+2·(-3)+9·(-4)+3·(-1)+5·3=-23$$ El número 1604928 si es divisible y se utiliza un dígito dos veces: $$8·1+2·(-3)+9·(-4)+4·(-1)+0·3+6·4+1·1=-13$$ El número abcabc es divisible por 13 independientemente de los valores a, b y c: $$1·c+(-3)·b+(-4)·a+(-1)·c+3·b+4·a=0$$
    • Un número es divisible por 11 si la diferencia entre la suma de las cifras impares y la suma de las cifras pares es 0 ó un múltiplo de 11. Se puede iniciar por la derecha o por la izquierda.
    El número 57238 no es divisible y el número 945076 si es divisible: $$(5+2+8)-(7+3)=5 \wedge(9+5+7)-(4+0+6)=11$$ El número abcabc es divisible por 11 independientemente de los valoresa,b y c: $$(a+c+b)-(b+a+c)=0$$
    • Un número es divisible por 7 cuando la suma de los productos de las unidades, decenas, centenas... de dicho número por los dígitos de la lista {1,3,2.-1,-3,-2} respectivamente es 0 ó múltiplo de 7. No es el único criterio de divisibilidad.
    El número 3427 no es divisible y no se utilizan todos los dígitos de la lista:$$7·1+2·3+4·2+3·(-1)=18$$El número 864192 si es divisible y utiliza todos los dígitos:
    $$2·1+9·3+1·2+4·(-1)+6·(-3)+8·(-2)=-7$$El número abcabc es divisible por 7 independientemente de los valores a, b y c: $$1·c+3·b+2·a+(-1)·c+(-3)·b+(-2)·a=0$$
    • Veamos que al dividir el número abcabc por 7·11·13=1001 se obtiene el número abc:
    $$abc·1001= (100a+10b+c)·1001=100100a+10010b+1001c$$ $$=100000a+10000b+1000c+100a+10b+c=abcabc$$

    viernes, 29 de noviembre de 2019

    Matemagia (I)

    ¿Qué es la Matemagia? Es matemática asociada a la magia, presentada de forma amena y dinámica generando asombro y sorpresa. Se presentan tres 'trucos' que utilizan el álgebra elemental y el sistema de numeración decimal.
    • TRUCO I: En una baraja asignamos un número a cada uno de los palos (1=oros, 2=copas, 3=bastos, 4=espadas) y un número a cada carta (8=sota, 9=caballo, 0=rey). Eliges una carta de la baraja y haces los siguientes cálculos: multiplica el número del palo por 2, suma 3 al resultado, multiplica el nuevo resultado por 5 y súmale el número de la carta. Ahora, díme el número obtenido.
    • ¡Sé la carta que has elegido!

    EXPLICACIÓN:
    Sea el rey de copas la carta elegida (2=palo, 0=carta). Hacemos los cálculos: (2·2+3)5+0=35. Ahora  hacemos 35-15=20. La decena es el palo y la unidad la carta. Sea el 7 de bastos la carta elegida (3=palo, 7=carta). Hacemos los cálculos: (3·2+3)5+7=52. Ahora  hacemos 52-15=37. La decena es el palo y la unidad la carta.

    ¿Por qué siempre hay que restar 15?

    Si x es el número del palo e y el número de la carta, se tiene: $$(2x+3)5+y=10x+15+y$$ Si restamos 15 obtenemos el número: $$10x+y=xy$$ y así sabemos que la decena es el palo y la unidad la carta.
    • TRUCO II: Lanza un dado y multiplica el resultado por 2, súmale 5 y vuelve a multiplicar el resultado por 5. Lanza otro dado y suma el resultado al anterior. Multiplica el resultado por 10 y súmale el resultado de lanzar un tercer dado.
    ¡Sé el resultado de tus dados!

    EXPLICACIÓN:
    Supongamos que las tiradas han dado los números 3, 6 y 1. Entonces ((2·3+5)5+6)10+1=611. Le quitamos 250 y obtenemos el 361. Y si el resultado de las tiradas es 4,4,5. Entonces ((2·4+5)5+4)10+5=695. Le quitamos 250 y obtenemos el 361. por tanto siempre conocemos el resultado de los dados.
    ¿Por qué  siempre hay que restar 250?

    Si x, y, z son los resultados de las tres tiradas se tiene: $$(2x+5)5+y=10x+25+y$$ $$(10x+y+25)10+z=100x+10y+z+250$$ Si restamos 250 obtenemos el número: $$100x+10+z=xyz$$ y así sabemos que la centena es el resultado del primer dado, la decena del segundo y la unidad del tercero.

    Piensa un número de tres cifras diferentes, invierte sus cifras y resta el número mayor del número menor. Invierte sus cifras y resta de nuevo estos dos últimos números.

    ¡Sé qué número has obtenido!

    EXPLICACIÓN:
    Sea un número de tres cifras con la única condición que la cifra de las unidades y la de las centenas no sean la misma. Por ejemplo 572 y invertimos sus cifras y restamos el mayor del menor: 572-275=297. Ahora invertimos las cifras del número obtenido y sumamos ambos números: 297+792=1089. Escogemos ahora el número 736 y repetimos el proceso: 736-637=099. 099+990=0189.
    ¿Por qué  siempre se obtiene el número 1089?

    Sea el número abc con a>c: $$abc-cba=(100a+10b-c)-(100c+10b+a)=99(a-c)$$ Como las cifras van de 0 a 9, se tiene que: $$1 \leq a-c\leq 9 \rightarrow a-c=k \rightarrow 1 \leq k \leq 9$$ El número obtenido se puede expresar de la forma siguiente: $$99k=100k-k=100(k-1+1)-k=100(k-1)+100-k=$$ $$100(k-1)+90+10-k=100(k-1)+9·10+10-k$$ Como: $$1 \leq k \leq 9 \rightarrow 1 \leq 10-k \leq 9$$ El número tiene 10-k unidades, 9 decenas y k-1 centenas. Invirtiendo sus cifras se tiene el número: $$100(10-k)+9·10+k-1$$ Sumando ambos números se tiene: $$100(k-1+10-k)+10(9+9)+10-k+k-1=$$ $$100·9+18·10+9=900+180+9=1089$$ y por tanto se obtiene siempre 1089, independientemente del número elegido inicialmente.

    martes, 28 de mayo de 2019

    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.