Matemáticas Educativas: matemática discreta

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

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.

viernes, 26 de abril de 2019

Aritmética Lunar (I)

Marc LeBrun introdujo la llamada Aritmética Lunar, antes conocida como Aritmética `triste' (`Dismal' Arithmetic). En esta Aritmética sólo se puede sumar y multiplicar.

La regla para sumar dos dígitos es: $$a+b=max(a,b)$$ La regla para multiplicar dos dígitos es: $$a \times b=min(a,b)$$ A continuación se muestra el resultado de un par de sumas y multiplicaciones:

El resultado de los cuadrados de los primeros números es:

Se sabe que un número primo es aquel que sólo puede obtenerse como producto de sí mismo por el elemento unidad (el uno). Pero en esta aritmética el elemento unidad es el nueve. En las multiplicaciones siguientes se observa que ni el 1 ni el 7 pueden ser el elemento unidad. Sin embargo se ve que cualquier número multiplicado por el 9 da de resultado ese número.

A continuación se muestran los primeros números primos:

Vamos a probar que el número 109 es primo. Supongamos que no lo es, entonces deberá expresarse como producto de dos números ab y cd. El dígito a (o el c) debe valer 1 para poder conseguir que el producto empiece por 1. Además los dígitos b y d deben valer 9 para que el producto termine en 9. Al terminar la multiplicación se observa que c debería valer 0, pero eso obliga a que el producto no empiece por 1. Por contradicción se concluye que el número 109 es primo.

Existen infinitos números primos en la Aritmética Lunar. Para saber más cosas de los primos lunares en La Enciclopedia de Secuencias de Enteros.

lunes, 26 de noviembre de 2018

Algoritmo de Moessner

El algoritmo, propuesto por el matemático Alfred Moessner en 1951 (aunque el resultado sería demostrado por Oskar Perrone al año siguiente), permite obtener las sucesiones de potencias de números naturales (como por ejemplo, la sucesión de los cuadrados, 1, 4, 9, 16, 25,…) a partir de la sencilla sucesión de los números naturales (1, 2, 3, 4, 5,...). Este método, de gran belleza, aparece en el libro The book of numbers de los matemáticos John H. Conway y Richard K. Guy.

En la serie de los números naturales eliminamos los múltiplos de 2 (dejamos un número y eliminamos el siguiente), y con los números resultantes se hacen las sumas acumulativas, obteniendo los cuadrados de los números naturales.

Ahora eliminamos los múltiplos de 3 (dejamos dos números y eliminamos el siguiente). Con los números resultantes dejamos uno y eliminamos el siguiente. Finalmente, con los números resultantes se hacen las sumas acumulativas, obteniendo los cubos de los números naturales.

Ahora eliminamos los múltiplos de 4 (dejamos tres números y eliminamos el siguiente). Con los números resultantes dejamos dos y eliminamos el siguiente.Con los números resultantes dejamos uno y eliminamos el siguiente. Finalmente, con los números resultantes se hacen las sumas acumulativas, obteniendo las cuartas potencias de los números naturales. Y así sucesivamente...

Sin embargo, este tipo de construcción se puede aplicar a situaciones más generales aún. Por ejemplo, ¿qué ocurriría, en la construcción de Moessner, si en lugar de mantener fija la distancia entre los números eliminados, se fuese incrementando dicha distancia. Un primer caso podría ser que se incremente en una posición la distancia anterior entre los números eliminados. En este caso obtendríamos los factoriales de los números naturales.

lunes, 6 de agosto de 2018

Números de Catalan

Fue el gran Leonhard Euler (1707-1783) la primera persona en calcular los denominados números de Catalan. Le comunicó los primeros valores a Johann Segner (1704-1777), pero no le dijo la técnica que utilizó para calcularlos. Segner obtiene estos números, por recurrencia, al estudiar las posibles triangulación de un polígono.

Una triángulación de un polígono es una forma de descomponerlo como una unión disjunta de triángulos cuyos vértices coinciden con los del polígono. Es fácil ver que para triangular un polígono de n+2 vértices se necesitan n triángulos y viceversa.

Sea Cn el número de maneras de descomponer un polígono utilizando exactamente en triángulos. Como se observa en la imagen: $$C_1=1, C_2=2, C_3=5, C_4=14 $$

La fórmula de recurrencia, dada por Signer en 1758, para obtener los números de catalán es: $$C_{n+1}=C_0·C_n+C_1·C_{n-1}+C_2·C_{n-2}+\cdots+C_{n-1}·C_1+C_n·C_0$$ siendo $$C_0=1$$
Demostración por inducción:

Si sabemos triangular los polígonos de n+2 lados, entonces podemos triangular un polígono de n+3 lados.

El polígono tiene los vértices 1,2,3,...n+3 y escogemos un 'lado favorito': el lado de vértices 1 y n+3, que pertenece a un triángulo Ti de la triangulación, siendo i el tercer vértice que pertenece al conjunto {2,3,...n+2}.

En la figura se observa que sería el triángulo de vértices 1,4 y 8.

En general, si se elimina ese triángulo Ti, resultan dos polígonos:

Vértices 1,2,...i que puede ser triangulado de Ci-2 maneras.
Vértices i,i+1,,...n+3 que puede ser triangulado de Cn-i+2 maneras.

Ambas elecciones son independientes, por tanto la manera de triangular el polígono que contiene al triángulo Ti es:
$$C_{i-2}·C_{n-i+2}$$
Al variar Ti sobre todos los valores posibles {2,3...n+2} se obtiene la fórmula.

Alrededor de un siglo después Eugène Catalan (1814-1894), volverá a calcular el número de maneras de triangular un polígono. En su memoria, esos números llevan su nombre.

Es una fórmula que evita la recurrencia y permite obtener directamente los números:

$$C_n=\frac{1}{n+1} \binom{2n}{n}=\frac{(2n)!}{(n+1)!·n!} \wedge n\geq 0$$
A partir de esta fórmula se puede obtener una fórmula de recurrencia más sencilla:
$$\frac{C_{n+1}}{C_n}=\frac{(2n+2)!}{(n+2)!(n+1)!}:\frac{(2n)!}{(n+1)!n!}=\frac{2(2n+1)}{n+2}$$
$$C_{n+1}=\frac{2(2n+1)}{n+2}{C_n}\wedge n\geq 1$$

Existen infinidad de situaciones en las que aparecen los números de Catalan. Una de ellas es el número de caminos monótonos crecientes a través de una retícula de tamaño nxn y que no atraviesen la diagonal:

Las aplicaciones sucesivas de un operador binario pueden representarse con un árbol binario.

En este caso, C_n es el número de árboles binarios de n + 1 hojas, en los que cada nodo tiene cero o dos hijos:

En su página de internet Richard Stanley, nos reta con 95 familias de objetos enumerados por los números de Catalan.

lunes, 26 de febrero de 2018

Principio de Wardrop

Supongamos que 1000 vehículos desean ir de A a B y tienen dos formas de hacerlo: ACB (ADB). Ambas rutas tienen un tramo de autopista AC (DB) en los que se tarda un tiempo que no depende del número de vehículos debido a su alta capacidad y un tramo CB (AD), que al ser una vía convencional, en el que el tiempo aumenta 1 minuto por cada 100 vehículos que la transitan.

Si se elige la ruta ACB:

$$t_{AC}+t_{CB}=t_{AC}+\frac{X_{CB}}{100}$$ Si en esta ruta se tardan 15 minutos por autopista y circulan 600 vehículos, el tiempo total empleado será: $$t_{ACB}=15+\frac{600}{100}=21$$

Si se elige la ruta ADB:
$$t_{AD}+t_{DB}=\frac{X_{AD}}{100}+t_{DB}$$

Si en esta ruta se tardan 10 minutos por autopista y circulan 400 vehículos, el tiempo total empleado será: $$t_{ADB}=\frac{400}{100}+10=14$$ Una parte de los conductores, los más avispados, que fueron por la ruta ACB eligirán la próxima vez la ruta ADB que es más rápida. Esto hará que ahora la ruta ADB sea más rápida (menos vehículos) pero la ruta ADB no lo sea tanto (más vehículos). El proceso seguirá hasta alcanzar un equilibrio que se producirá cuando los tiempos de viaje sean los mismos para ambos trayectos. A nadie le interesará cambiar en el próximo viaje.

Estamos ante un Equilibrio de Nash de la teoría de juegos: no hay cambio de estrategia individual que permita a un jugador aumentar su 'ganancia'.

En el ejemplo: $$t_{ACB}=t_{ADB}$$ $$15+\frac{250}{100}=\frac{750}{100}+10=17.5$$
Principio de Wardrop (1952):

Los tiempos de viaje en todas las rutas es igual (entre ellas), y menor al tiempo que experimentaría cualquier vehículo que decidiera cambiar a otra ruta.

Descargar .XLS

Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:

Con las flechas se puede modificar el número de vehículos iniciales por la ruta A.
Con las flechas se obtiene la evolución de los tiempos y vehículos en cada ruta.
Con la flechas se pueden fijar los tiempos por autopista.
Se muestran los valores de equilibrio de tiempo y vehículos.

lunes, 27 de noviembre de 2017

Algoritmo de Irving

El llamado The Stable Rommates Problem o 'Problema de las Compañeras de Piso' fue resuelto mediante un algoritmo por Robert W. Irving en 1985. Cada participante ordena a sus posibles compañeras según sus preferencias. Cada chica elige una compañera y ésta acepta o no la oferta. En caso de no aceptar se entiende que rechaza a la chica que le ha hecho la propuesta. En el ejemplo de la tabla el AZUL indica la elegida, el VERDE la que acepta y el ROJO la rechazada.

1ª ETAPA

Cada chica propone a su compañera favorita.
La elegida acepta, pero si es elegida por más de una, acepta la mejor propuesta y rechaza las demás.
Las rechazadas esperan para ser aceptadas más adelante.
Si alguna chica es rechazada por todas no existe una solución estable.

Aunque Berta elige a Delia, ella prefiere a Clara y es rechazada. Igualmente, aunque Eva elige a Flor, ella prefiere a Delia y es rechazada.

Ahora Berta propone a Eva que acepta y Eva propone a Clara que acepta.

2ª ETAPA

Todas desechan las posibles compañeras que son menos deseadas que la actualmente aceptada.

Ana rechaza a Clara y a Eva, Berta rechaza a Clara, y así sucesivamente.

Así las opciones quedan reducidas a las siguientes:

3ª ETAPA

Elige una participante X que tenga al menos dos opciones.
Busca su segunda preferencia Y.
Sea Z la última preferencia de Y.
Repite el proceso hasta que se llegue a X.
Elimina las parejas (Y,Z) y sus simétricas.
Repite el proceso hasta que todas tengan una única opción.

Los emparejamientos son: Ana y Flor, Berta y Eva, Clara y Delia.

En este caso no hay una solución estable, pues nadie quiere ir con D.

Páginas

viernes, 6 de diciembre de 2024

jueves, 30 de noviembre de 2023

miércoles, 19 de abril de 2023

lunes, 29 de agosto de 2022

viernes, 21 de enero de 2022

lunes, 27 de septiembre de 2021

lunes, 2 de agosto de 2021

miércoles, 19 de mayo de 2021

viernes, 16 de abril de 2021

domingo, 21 de febrero de 2021

domingo, 4 de octubre de 2020

jueves, 13 de agosto de 2020

jueves, 16 de enero de 2020

viernes, 29 de noviembre de 2019

martes, 28 de mayo de 2019

viernes, 26 de abril de 2019

lunes, 26 de noviembre de 2018

lunes, 6 de agosto de 2018

lunes, 26 de febrero de 2018

lunes, 27 de noviembre de 2017