Usuario:Óscar Baños Campos/Taller

Demostración recurrente y por inducción.[editar]

Tengamos un plato de Hanoi con tres varillas colocadas tal que la primera contenga los n discos ordenados y las otras dos varillas no contengan nada.

Empecemos definiendo el ejercicio más básico, tenemos un solo disco, por tanto el movimiento del primer plato al último es 1 solo paso.

$a_{1}=1$

$a_{0}=0$ pues con 0 discos no hay movimiento que hacer; para realizar la demostración no es necesario considerar este resultado pues no tiene sentido 0 discos Hanoi.

Para dos discos tenemos que mover el pequeño a la varilla auxiliar, el grande a la final y el pequeño a la final para un total de 3 pasos.

$a_{2}=3$

Para tres discos tenemos que

$a_{3}=7$ movimientos necesarios mínimos.

Para la resolución de este ejercicio se pueden aplicar dos caminos diferentes. La resolución de la ecuación de recurrencia general que nos permitirá hallar las raíces de un polinomio y sus coeficientes para calcular posteriormente una función f(n) que nos devuelva un número exacto de movimientos dados para n discos o aplicar recurrencia para tratar por intuición el resultado final:

Fórmula general:[editar]

Tengamos un estado $a_{n}$ que denota la cantidad de movimientos a realizar para n discos.

Para hallar la ecuación hay que aplicar una hipótesis.

Sabemos que para un disco se necesita un movimiento, para dos discos tres movimientos y para tres discos se necesitan siete movimientos.

Suponemos la hipótesis que para mover n discos se tiene que mover los (n-1) discos anteriores y uno más que es el disco n.

Además sabemos que esos discos deben moverse el doble de veces pues para 2 discos, hay que mover el disco pequeño dos veces, una para quitarlo de la cima y otra para ponerlo en la cima al final.

Para tres discos es exactamente lo anterior, debemos mover los 2 discos menores 2 veces, una para quitarlos de encima del disco grande, 1 movimiento para mover el disco grande a la varilla final, y otra vez volver a mover los dos discos encima del disco grande.

Por tanto la fórmula final que nos queda es:

$a_{n}=2*a_{n-1}+1$

Reordenándola:

$a_{n}-2*a_{n-1}-1=0$

Es una ecuación sencilla que se podría resolver fácilmente y llegar a la conclusión que para n discos dados los movimientos son: $a_{n}=2^{n}-1$ Sin embargo, vamos a resolverla paso por paso para estudiarla.

En este caso podemos convertir los término dependientes de cada iteración en raíces polinomiales teniendo en cuenta que el grado del polinomio será del orden del menor término que haya presente, en este caso $a_{n-[1]}$ tomamos el 1 como grado del polinomio pues el menor término es $a_{n-1}$ , si hubiese un $a_{n-k}$ k sería el grado del polinomio.

Antes de eso hay que tomar su homogénea asociada, es decir suprimimos el término independiente:

$a_{n}-2*a_{n-1}=0$

Reescribimos la ecuación correspondiente: sustituyendo $Dado\,\,k\,\,\{0,1,...,rank(pol)\}\in a_{n-k}\implies r^{rank(pol)-k}:$

$r-2=0$

Por tanto la raíz característica de dicha ecuación resulta ser:

$r=2$

En este caso solo tenemos una raíz simple son multiplicidad 1.

Tenemos por tanto que aplicando la fórmula general:

$a_{n}=C*r_{n}^{n}:r=2$ En este caso solo existe una r, por tanto, $a_{n}=C*2^{n}$ donde falta hallar el coeficiente C

Ahora falta recuperar la no homogénea, es decir hay que recuperar: $a_{n}-2*a_{n-1}-1=0$ .

Realizando un cambio de variable:

$a_{n}^{p}\,\,=\,\,B\,\,=\,\,2*B\,\,+\,\,1$ , por lo tanto $B=-1$ .

Recuperamos la homogénea asociada con $B=-1$ y hallamos su resultado:

$a_{n}=C*2^{n}-1$ .

Igualamos a las condiciones iniciales.

$a_{1}=C*2^{n}-1\implies 1=C*2^{1}-1\implies C={\frac {1+1}{2^{1}}}\implies C=1$


Nota: Se puede realizar también con  $a_{0}=0$  pero como tal una torre de Hanoi con 0 discos carece de sentido por lo que se utiliza  $a_{1}=1$  que es el primer elemento  de la sucesión. Si se utilizase otro  $a_{k}:k\in \{1,2,...,n\}$  el resultado no coincidiría pues es un polinomio de grado uno y se esta utilizando un elemento de la sucesión que supera dicho rango.

Por tanto el resultado final obtenido es:

$a_{n}=2^{n}-1$

Comprobación por Intuición.[editar]

Para la inducción débil partimos de la misma premisa que en la fórmula general pero en este paso utilizaremos otro método de verificación que en casos más sencillos como este ejercicio puede resultar más útil pero no es válido para todo tipo de sucesiones o ecuaciones en diferencia.

Tenemos un primer movimiento: $a_{1}=1$ .

y previamente debido a la anterior demostración sabemos que para el movimiento $a_{n}=2*a_{n-1}+1$ .

Por tanto vamos a efectuar una concatenación de movimientos.

$a_{1}=1$

$a_{2}=2*a_{1}+1$

$a_{3}=2*a_{2}+1$

$a_{n}=2*a_{n-1}+1$

Aplicando recurrencia descendente podemos llegar a la conclusión que

$a_{n}=2*a_{n-1}+1=2*(2*a_{n-2}+1)+1=2*(2*(2*a_{n-3}+1)+1)+1$

$a_{4}=2*a_{3}+1=2*(2*a_{2}+1)+1=2*(2*(2*a_{1}+1)+1)+1$

El siguiente paso es el deductivo y es el más importante pues una mala deducción llevara a un resultado.

Podemos observar que para $a_{n}$ tenemos un 2 multiplicando $a_{n-1}$ y un 1 sumando.

si hacemos lo mismo en $a_{n-1}$ obtenemos el mismo resultado respecto a $a_{n-2}$ .

Vemos que para n elementos dados obtenemos (n-1) 'doses' multiplicándose entre sí y (n-1) 1 multiplicados por sucesivos 'doses' tenemos que

$a_{n}=2^{n-1}+\sum _{k=0}^{k=n-2}2^{k}=2^{n-1}+2^{n-1}-1=2^{n}-1$

En este caso la dificultad proviene en hallar el resultado de la suma sucesiva de potencias de orden 2, $1+2+4+8+n-2=2^{n-1}-1$

En último caso podemos aplicar inducción débil para verificar que el resultado obtenido es el correcto:

Inducción débil.[editar]

$a_{n}=2^{n}-1$

Paso base: k=1

$a_{1}=2^{1}-1=1$

Paso inductivo:

$a_{k}=2^{k}-1$ ¿Se verifica $a_{k+1}=2^{k+1}-1$ ?

$a_{k+1}=2*a_{k}+1$ ; pues $a_{k}=2^{k}-1$ ; $a_{k+1}=2*\{2^{k}-1\}+1=2*2^{k}-1=2^{k+1}-1$

Se verifica por inducción la veracidad de la fórmula.

Llegamos a la conclusión que ambos métodos son igualmente válidos para obtener la cantidad de movimientos necesarios para n discos dados ordenados en la primera varilla.

PERMUTACIONES CIRCULARES: Definición:

Demostración práctica[editar]

    Supongamos una reunión de n personas que se sientan en torno a una mesa circular con n sillas, una silla para cada persona, ¿De cuántas formas diferentes se pueden distribuir las personas en los asientos disponibles teniendo en cuenta que la mesa es circular?

Para ello se requiere que los asientos sean indistinguibles, es decir, si solo se sentase una persona no importa en cual de ellos se siente pues una circunferencia no tiene principio ni final, solo se le asigna un punto arbitrario como referencia. Los objetos a colocar deben ser distinguibles o en su caso de multiconjuntos distinguibles de elementos indistinguibles, ejemplo el conjunto $C_{1}$ = {1, 1, 1} El orden importa, pues no es lo mismo que una persona se siente a la derecha o a la izquierda de otra.

Teniendo esto en cuenta se toma la primera n-persona como punto de referencia sentándola en una silla cualquiera de la mesa, después de esto se coloca la siguiente n - 1 persona en otra n-1 silla de las disponibles, se repite el mismo proceso para la (n-2), (n-3) ... (n-n) personas con lo cual al final al aplicar la propiedad multiplicativa obtenemos que las permutaciones cíclicas de n elementos son $PC_{n}=(n-1)!$ formas diferentes.

Ejemplos prácticos:[editar]

   Dadas 5 personas en torno a una mesa redonda, ¿De cuántas formas distintas podemos sentarlas?

En este caso estamos ante una permutación circular sin restricción ni condición alguna, para ello procedemos a asignar a un elemento una posición concreta de la mesa para tomarlo como punto de referencia y permutamos a los restantes en torno a él, esto nos deja con $PC_{5}=(5-1)!=4!=24$ formas distintas pues lo que se debe permutar son los demás elementos del conjunto.

   Dadas 5 personas (Sean llamadas S,T,U,V,W) en torno a una mesa redonda tal que la persona S y T sean pareja y quieran sentarse siempre juntas, ¿De cuántas formas distintas podemos sentarlas?

En este caso tenemos 4 elementos dentro del conjunto, 3 personas sean U, V y W y otras dos que forman un multiconjunto $(S,T)$ tomamos una de ellas como punto de referencia y permutamos al resto alrededor de ella para obtener las posibles combinaciones, en este caso tenemos un total de $PC_{4}=(4-1)!=6$ formas distintas

Pero ahí no acaba el ejercicio pues hay que recordar que el multiconjunto (S,T) también puede ordenarse pues no es lo mismo que T vaya a la izquierda de S que a la derecha, esto nos da 2 formas totales de ordenarlos. Para resolver el ejercicio hay que aplicar el principio de la multiplicación, no el de la adición, pues S y T también deben sentarse a la vez que el resto de personas, no son un grupo separado que puede o no sentarse en la mesa por tanto el resultado final del ejercicio sería:

6*2 = 12 formas de sentar a 5 personas tal que 2 de ellas formen una pareja.

Por tanto a la hora de aplicar permutaciones cíclicas, hay que definir en torno a que elementos se van a permutar el resto de elementos pues si no se trataría de una permutación sin punto de referencia o permutación genérica. La conclusión es que dadas n personas, la permutación cíclica necesita al menos 1 elemento de referencia a permutar por lo tanto la fórmula estándar final queda:

$PC_{n}=(n-1)!$

Ejemplo concreto:[editar]

Tomemos una mesa de 4 personas, S,T,U,V

primero fijamos la persona S y permutamos en un ciclo las otras 3:

Obtenemos:

Fijando S. $D_{S}=\{(S,T,U,V),(S,V,T,U),(S,U,V,T)\}$ El cardinal de $|D_{S}|=3$

Tomamos la persona T y permutamos de nuevo obteniendo:

Fijando T. $D_{T}=\{(T,V,S,U),(T,S,V,U)\}$ El cardinal de $|D_{T}|=2$

Tomamos la persona U y permutamos de nuevo:

Fijando U. $D_{U}=\{(U,S,T,V)\}$ El cardinal de $|D_{U}|=1$

La suma de los cardinales es igual a 6, resultado de la permutación de $PC_{4}=(4-1)!=6$

Breve explicación:[editar]

Si tratásemos de fijar la última persona, V, y permutáramos el resto de elementos, obtendríamos una permutación cíclica ya presente, pues en las permutaciones cíclicas

$\{0,1\}=\{1,0\}$

Ya que en las permutaciones cíclicas o circulares los elementos de los "extremos" están relacionados, es decir, en el primer ejemplo a la derecha del 0 se va al 1 y en el segundo ejemplo a derecha del 0 también se va al 1 pues es un mismo ciclo.

Para entender esto, hay que destacar que en una permutación cíclica no existen primer y último elemento, tampoco se distinguen a los elementos en función de su posición de colocación sino respecto a como se encuentra su estado de permutación respecto al resto de elementos, imagínese que el conjunto $C=\{1,2,3,4,5\}$ el 1 tiene a su izquierda el 5 y a su derecha el 2, el 2 por su parte tiene a su izquierda el 1 y el 3 a su derecha y así sucesivamente por tanto todas las permutaciones $\{1,2,3,4,5\}=\{5,1,2,3,4\}=\{4,5,1,2,3\}=\{3,4,5,1,2\}=\{2,3,4,5,1\}$ son en realidad la misma pues todos los elementos ocupan la misma posición respecto al resto de elementos.

Enlaces externos:[editar]

Página web (Matemovil: Vídeo): Explicación breve y ejercicios sobre diferentes permutaciones circulares.

Página web (Superprof): Breve explicación y unos ejercicios resueltos.

Blogspot (matematicasn): Explicación más detallada con ejercicios y vídeo.

TEMA 1. FUNDAMENTOS:[editar]

Funciones: Funciones Hash y su uso en la criptografía.

Definición de función Hash[editar]

Una función Hash comúnmente denotada H, es una función para la cual un elemento de un conjunto se proyecta sobre otro conjunto asegurando que para el elemento del primer conjunto le corresponde un único elemento del conjunto imagen, en cambio a los elementos del conjunto imagen les pueden o no corresponder uno, varios o incluso ningún elemento del primer elemento.

Cuando a un elemento del conjunto imagen le corresponden múltiples elementos del conjunto generador al cual se le aplica la función se dice que existen colisiones.

$f:A\rightarrow B$

$h(x)\rightarrow y$

(Siendo x comúnmente llamada llave e y clave)

Uso de las funciones SHA[editar]

Una característica principal de las funciones SHA es la capacidad de no reflexividad, es decir, dado una cadena de bits del buffer de salida resulta prácticamente imposible intentar hallar una cadena origen que devuelva el mismo contenido, además de disponer de una gran cantidad de combinaciones posibles que evitan que se puedan dar duplicado de datos o colisiones las cuales pueden comprometer la seguridad de diferentes archivos.

Las funciones SHA permiten la creación de cadenas diferentes que facilitan seguir un registro de cambios en la seguridad de diferentes archivos conocida como huella digital, esto sirve de especial importancia en aplicaciones tales como la creación de cuentas asociadas a contraseñas que solo un usuario debe conocer, claves de desencriptado de ficheros o usos en la creación de cadenas de bloques en criptomonedas como el bitcoin.

En teoría una función SHA perfecta no debería tener ninguna colisión pero debido a que están pensadas para trabajar con cadenas de texto indeterminadas, las posibilidades de que exista una colisión imprevista no son nulas pero si son increíblemente bajas pues, tomando el ejemplo de SHA-1 de 160 bits tendríamos hasta $2^{160}$ combinaciones posibles el cual es un número tan grande que esperar que se dé una colisión de manera fortuita resulta inviable, sin embargo no significa que sea totalmente seguro pues con métodos avanzados se ha logrado desencriptar sin necesidad de recurrir a ataques de fuerza llegando a encontrar colisiones y forzando a la creación de nuevas formas de encriptado para aumentar la seguridad.

$Hash(cadena,sLL)=clave$

$verificacion(cadena,clave,pLL)=Verdadero/Falso$

La primera permite a un usuario crear una firma digital para verificar que un mensaje dentro de una transacción ha sido emitida por él mismo y la segunda permite que el receptor verifique que el emisor fue el autor original de dicha transacción.

Esta firma digital permite crear un sistema de confianza el cual se basa en que si ningún otro usuario conoce tu llave secreta, nadie podrá ser capaz de falsificar una transacción realizada a tu nombre. La importancia radica en que la firma digital varia con cada mensaje, es decir que para cada transacción de una criptomoneda se tendría que crear una nueva clave de la cual solo el usuario original conoce la llave secreta, debido a que el SHA de mayor uso extendido es de 256 bits (bitcoin lo utiliza aunque algunas otras criptomonedas utilizan el 512 bits para seguridad añadida) eso deja una posibilidad de 1 entre $2^{256}$ posibles combinaciones.

Este número es lo suficientemente grande como para evitar que se pueda buscar una llave probando combinaciones y asegurar que la probabilidad de colisión sea tan baja que resulte inviable encontrar un brecha, cabe mencionar que a día de hoy sigue sin haberse encontrado una brecha o colisión que provoque una vulnerabilidad al sistema. pero si se llegó a encontrar en SHA menores como el de 160 bits o 128.

TEMA 2. TEORIA DE NUMEROS[editar]

Números primos y Teorema de Dirichlet[editar]

El teorema de Dirichlet sobre progresiones aritméticas es un resultado de la teoría analítica de números demostrado por el matemático Dirichlet. Este teorema sobre la distribución de los números primos en $\mathbb {N}$ , fue conjeturado por Gauss y finalmente demostrado en 1837 por Dirichlet, nombre por el que actualmente se le conoce.

Enunciado[editar]

Sea $a,\,d\in \mathbb {N}$ tal que el máximo común divisor $\operatorname {mcd} (a,d)=1$ , entonces la progresión aritmética $a_{n}=a+n\cdot d$ contiene infinitos números primos.

Dirichlet

Esto quiere decir que los números a+nd forman una progresión aritmética

a,\ a+d,\ a+2d,\ a+3d,\ \dots ,\

en la que hay infinitos números primos, o dicho de otra manera, hay infinitos números primos congruentes con a módulo d.

Por ejemplo, el teorema asegura que hay una cantidad infinita de números primos que terminen en 7, ya que los números que terminan en 7 forman una progresión aritmética (7, 17, 27, 37, ...) es decir, es una sucesión de números de la forma a+nd con a=7 y d=10, siendo estos primos entre sí, luego su máximo común divisor es 1.

Enunciado extendido[editar]

El enunciado anterior esta formulado para la base decimal o base 10 pero se puede extender a diferentes bases.

$Sea\,a,b\in \mathbb {N} \,\,\,\,b\,una\,base\,numerica,\,mcd(a,b)=1$

Siempre que a sea $a\in {2,3,...,(b-1)}$ es decir, a está comprendida entre el menor número primo, 2, y el número menor inmediato a la base, obtendremos distintas clases de congruencias en dicha base.

Es decir, aquellos número coprimos con la base b serán válidos para verificar que $a_{n}=a+n*b$ ,solo es necesario comprobar con las primeras clases pues, tomando el ejemplo de la base 10

$mcd(7,10)=1$ podemos afirmar que en la sucesión 17, 27, 37... habrá números primos, al igual con la sucesión de la clase del 1,3 y 9 pero sería redundante aplicarlo a la clase del 17 que esta contenida a su vez en la del 7.

De aquí se puede deducir aplicando la función $\phi$ de Euler para la base b, habrá 'd' distintas clases de equivalencias.

En la base decimal

$\phi (10)=4$ clases de equivalencia distintas que son 1,3,7,9 es decir, todos los números acabados en esas cifras o que sean pertenecientes a su clase de equivalencia podrán ser números primos.

Esto se debe a que la función de Euler se puede utilizar para calcular la cantidad de número coprimos a un número dado, en el caso del 10 son 4 número coprimos.

Para ilustrar el teorema extendido a bases numéricas diferentes tomemos el ejemplo de la base 10 o decimal.

cuando hacemos una tabla que contiene a los números naturales nos fijamos

que solo los número acabados en 1, 3, 7 o 9 pueden ser número primos (a excepción del 2 y 5) pues todos los demás que acaben en cifra par o 5 serán múltiplos de estos números

Esto es fácilmente visualizable pues el 10 esta compuesto por 2 y 5; $10=2*5$


0 mod 10	0	10	20	30	40	50	60	70	80	90
1 mod 10	1	11	21	31	41	51	61	71	81	91
2 mod 10	2	12	22	32	42	52	62	72	82	92
3 mod 10	3	13	23	33	43	53	63	73	83	93
4 mod 10	4	14	24	34	44	54	64	74	84	94
5 mod 10	5	15	25	35	45	55	65	75	85	95
6 mod 10	6	16	26	36	46	56	66	76	86	96
7 mod 10	7	17	27	37	47	57	67	77	87	97
8 mod 10	8	18	28	38	48	58	68	78	88	98
9 mod 10	9	19	29	39	49	59	69	79	89	99

En este caso tenemos 4 clases de equivalencias que se corresponden al residuos 1, 3, 7, 9 congruentes con módulo 10

$X\equiv 1(mod10)$

$X\equiv 3(mod10)$

$X\equiv 7(mod10)$

$X\equiv 9(mod10)$

Cualquier X que verifique dicha congruencia podrá ser número primo, es decir, si un número no cumple con lo anterior podemos afirmar que es imposible que sea número primo.

Una conclusión que se puede extraer es que para todas las clases tendrán un número aproximado de primos, es decir, que dado un número primo aleatorio las probabilidades de que pertenezca a una clase o a otra son las mismas por tanto si fuésemos añadiendo números primos sucesivos observaríamos que se distribuyen equitativamente entre la clase del 1, 3, 7, 9 para la base 10 y esto se puede aplicar a cualquier base distinta.

De aquí se puede concluir que las distribuciones de números primos suelen tener un aspecto uniforme esto es fácilmente observable en distintas representaciones gráficas en las cuales los números primos tienen a formar grupos pero no es resultado de una propiedad de los números primos sino que a la hora de obtener diferentes clases de equivalencia los número primos se agrupan en las clases que son coprimas con la base en la cual se representa.

Demostración[editar]

La demostración del teorema utiliza las propiedades de ciertas funciones multiplicativas (conocidas como funciones-L de Dirichlet) y varios resultados sobre aritmética de números complejos y es suficientemente compleja como para que algunos textos clásicos de teoría de números decidan excluirla de su repertorio de demostraciones.^[1]