Bloque de Colores

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Icono de Post March 3 2012 :: Combinatoria, Lenguajes Formales, Lógica ::

Lo que estamos buscando es, dado A un alfabeto de tamaño k, la cantidad de cadenas de tamaño n que contienen exactamente m símbolos de A.

Para resolver este problema primero vamos a resolver lo siguiente:

Cuantas cadenas de tamaño n pueden ser creadas con todos los símbolos de un alfabeto de k símbolos?

Se propone la siguiente relación de recurrencia de 2 variables, donde:

n: representa el tamaño de la cadena

k: representa la cantidad de símbolos en el alfabeto

f(0, k) = 0

Para todo k, ya que la cantidad de cadenas de tamaño 0 que pueden formarse con todos los símbolos de A es 0.

f(1, 1) = 1

Ya que existe solo una cadena de tamaño 1 con 1 símbolo.

f(n, k) = k( f(n-1,k) + f(n-1, k-1) )

Demostración

Llamemos An,k al conjunto de todas las cadenas de tamaño n que contienen a todos los símbolos de A e intentemos construir todas las cadenas que pertenecen a este conjunto.

Para cada símbolo a de An,k vamos a realizar el siguiente procedimiento:

1. Llamemos An-1,k al conjunto de todas las cadenas de tamaño (n-1) con exactamente k símbolos de A (o sea con todos los símbolos de A).

Para cada cadena α de An-1,k construimos una nueva cadena concatenandole a, nos queda así una nueva cadena: . Como α tiene tamaño (n-1), la nueva cadena tiene tamaño n.

Ademas por definición de An-1,k, α contiene a todos los símbolos de A, y en particular contiene a a. Entonces de esta manera hemos formado todas las cadenas de An,k que comienzan por a y tienen al menos 2 ocurrencias de a.

Nos queda todavía construir todas las cadenas de An,k que comienzan por a pero tienen solo una ocurrencia de a.

2. Llamemos An-1,k-1 al conjunto de todas las cadenas de tamaño (n-1) que están formadas por todos los símbolos de A menos a.

Para cada cadena β de An-1,k-1 construimos una nueva cadena . Se cumple entonces que tiene tamaño n y ademas dado que β contiene a todos los símbolos de A menos a a y le hemos concatenado a, contiene los k símbolos de A.

A partir de estos dos pasos hemos construido todas las cadenas de An,k que comienzan con a. Como por definición de An,k, cualquier cadena de An,k necesariamente tiene que comenzar con un símbolo de A y a es un elemento arbitrario podemos aplicar el procedimiento para construir todas las cadenas del conjunto An,k.

Como por hipótesis, |An-1,k-1| = f(n-1,k-1), |An-1,k| = f(n-1,k) y como existen exactamente k símbolos de A se cumple que f(n, k) = k( f(n-1,k) + f(n-1, k-1) ).

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Asumiendo que la función anterior es correcta, podemos proponer la siguiente función:


g

(
n
,
m
,
k
)

=

(

m
k

)

×
f

(
n
,
m
)


Llamemos Am al conjunto de todos los subconjuntos de A con exactamente m elementos. Es conocido que la cantidad de subconjuntos de tamaño m de un conjunto se puede calcular como:


|

A
m

|
=

(

m
k

)


(Ver Combination) . Sabemos ademas por el resultado anterior que la cantidad de cadenas de tamaño n que pueden hacerse de un conjunto de tamaño m es igual a f(n,m), a partir de lo cual derivamos la formula.

Autor: Emiliano Martínez Luque.

Comments Off on Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Problema de Algoritmia Básico: Primera Solución

Icono de Post February 28 2012 :: Algoritmia, c, Estructuras de datos, Lógica ::

Este es una serie de posts sobre un ejemplo básico de analisis de algoritmos. Va a constar de 3 partes: Descripción del problema y solución básica, Análisis de complejidad de la solución básica y Posibles mejoras. El codigo de estos posts se puede encontrar aquí .

Hace unos días estuve hablando con un ex-compañero de la facultad sobre una entrevista de trabajo que había tenido en una empresa muy grande de estados unidos. Me comento muy rapidamente y sin muchos detalles sobre el problema que le habían presentado y me resultó interesante como un buen ejercicio de Algoritmia básica.

Descripción del problema

El problema consiste en dado una lista de numeros enteros, remover los duplicados de la lista. Asumí al hacer el codigo, que interesa mantener la estructura de la lista ( O sea dado una lista: [5,3,4,5,3,2]; encontrar la misma lista pero con los duplicados removidos: [5,3,4,2] ).

Obviamente el problema no es solamente solucionar este problema, sino razonar sobre la corrección y eficiencia de la solución encontrada y ademas codificarlo en algun lenguaje ( especificamente C ).

Algunos pasos previos

Antes de comenzar a trabajar en el problema, me parecio conveniente hacer algunas funciones para poder testear y probar el codigo.

Struct de la lista

La estructura de datos que se va a utilizar en el ejercicio


typedef struct Node *List;
struct Node {
  int value;
  struct Node *next;
};

Función para mostrar la lista

Una función para mostrar la lista por pantalla.


void mostrar_lista(List lista) {
	//Este primer paso es para el pretty print de la lista
	if(lista != NULL) {
		printf("%d", lista->value);
		lista = lista->next;
	}
	while(lista != NULL) {
		printf("-%d", lista->value);
		lista = lista->next;
	}
}

Función para cargar una lista de prueba

Una función que dado un string con una lista de enteros separados por comas, lo parsea a un linked list.

Esta es una versión mejorada sobre la que hice originalmente, esta versión es forgiving con aquellos caracteres que pueden haber sido mal tipeados por el usuario o por input malintencionado, tomando solo los caracteres que representan dígitos ( el string: “1,a2,3b,d4d,xxxx,5,,,,6,a8b0,10” se tranforma en la lista: [1,2,3,4,5,6,80,10] ). La versión original era un poco más simple y no anticipaba malas entradas.


List crear_lista(List lista, char str[2000]) {
	int i=0;
	List rList = lista;

	//Es forgiving, solo lee los digitos y descarta lo demas.
	while( str[i] != '' ) {
		while( str[i] != '' && (str[i] < '0' || str[i] > '9') ) i++;
		if(str[i] == '') break;

		int pre = 0;
	    
		//Calcular el int
		while( str[i] != ',' && str[i] != '' ) {
			if(!(str[i] < '0' || str[i] > '9')) { 
				pre = pre * 10;
				pre = pre + (str[i] - '0');
			} 
			i++; 
		}
	    
		//Crear el nodo nuevo    
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = pre;
		temp->next = NULL;

		//Primera iteracion
		if(lista==NULL) {
			//Agregar nodo a lista
			lista = temp;
			//Lista de retorno
			rList = lista;
		} else {
			//Agregar nodo, mover cursor.
			lista->next = temp;
			lista = lista->next;
		} 
		i++;
	}
	return rList;
}

Ejemplo de uso:


	char str[2000] = "";
	scanf("%s", str);
	lista = crear_lista(lista, str);
	printf("La lista es: n");
	mostrar_lista(lista);

Solución básica

La solución básica consiste de 2 funciones. Una función int esta_en_lista(int value, List *pasados) que dado un entero value y una lista pasados verifica si el valor existe en la lista. Si ya existe devuelve 1, si no, devuelve -1 (podría haber usado constantes TRUE y FALSE como macros y el codigo seria mas bonito) y agrega este valor a la lista pasados en orden ascendente. La lista pasados se pasa por referencia ( efectivamente es un puntero a puntero ) dado que como side effect de la función se modifica esta lista, agregandosele ordenadamente cualquier valor que no pre-existe. O sea, en sucesivas llamadas a la funcion se va creando una lista ordenada de valores. La otra función List * sacar_duplicados(List *lista, List *pasados), recibe 2 punteros a listas, la lista de enteros de la que queremos sacar duplicados y una lista donde se guardan los valores que ya existen en la lista. Esta es la función que devuelve la primer lista con los valores removidos. Esta pensado para ser llamada con pasados siendo una lista vacia.


//Version basica a ser mejorada
//Se pasa un puntero al puntero de lista para hacer los side effects
int esta_en_lista(int value, List *pasados) {

	List rList, prev;

	rList = *pasados;
	prev = NULL;

	if(rList == NULL) {
		//Agregarlo antes
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = value;
		temp->next = *pasados;
		*pasados = temp;
		return -1;
	}

	while(rList != NULL) {
		if(rList->value == value) return 1;
		if(rList->value > value) {
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = value;
			temp->next = rList;
			if(prev==NULL) {
				*pasados = temp;
			} else {
				prev->next = temp;
			}
			return -1;
		}
		prev = rList;
		rList = rList->next;
	}
	//Agregarlo al final
	List temp;
	temp = (List) malloc(sizeof(struct Node));
	temp->value = value;
	temp->next = NULL;
	prev->next = temp;
	return -1;
}



//ESTA ES LA FUNCION QUE IMPORTA EN UN PRIMER PASO
//EN UN SEGUNDO PASO LO QUE IMPORTA ES MEJORAR LA FUNCION ANTERIOR
List * sacar_duplicados(List *lista, List *pasados) {
	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} else {
	//PASO INDUCTIVO
		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}
	}
}

Se puede testear el programa compilando y corriendo solucion-basica.c .

Razonando sobre la corrección del algoritmo

Primera Parte

Lo primero que habria que considerar es si la función esta_en_lista() es correcta. No voy a hacer un análisis muy formal, pero supongamos los posibles casos:

  • pasados es una lista vacia: Se ejecuta el primer if: if(rList == NULL) , se crea un nodo nuevo que se agrega a pasados y se devuelve -1.
  • pasados no es una lista vacia y el valor existe en la lista:, se ejecuta el primer if y devuelve falso, se ejecuta la sentencia: while(rList != NULL) , se itera por todos los nodos hasta que se encuentra el nodo en el que pre-existe el valor, se llega a la condición: if(rList->value == value) y se devuelve 1.
  • pasados no es una lista vacia, el valor no existe en la lista y es menor a cualquier valor de la lista: se llega al while, en la primera iteración se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev fue inicializado a NULL y es la primera iteración, se asigna este nuevo nodo a pasados y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y esta entre medio de 2 valores de la lista: se llega al while, se itera por los nodos hasta que se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev esta apuntando al nodo pàdre del actual, se asigna este nuevo nodo como hijo de prev y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y es mayor a cualquier valor de la lista: se llega al while, se itera por los nodos hasta que se recorre toda la lista y se sale del while, se crea el nuevo nodo, se le agrega null como nodo hijo y se evalua la condición, se asigna este nuevo nodo como hijo de prev (que en este momento es el ultimo nodo de la lista) y se devuelve -1.

Razonar sobre la corrección del valor que devuelve (1 o -1) es trivial. Asi como razonar que no agrega un valor que ya existe.

Lo que es importante ver es que si se llama a la función con una lista ordenada y un valor que no existe en la misma, por los 3 ultimos casos (y el primero siendo estrictos, ya que una lista vacia es una lista ordenada), a esta lista se le agrega el valor en orden.

Segunda parte

Asumiendo que la función anterior es correcta y que la función esta_en_lista() devuelve un valor correcto y asi mismo que en sucesivas llamadas a la lista pasados se guardan en esta todos los elementos anteriores, podemos razonar sobre la función sacar_duplicados() que es la que nos importa.

La función es recursiva, por lo que para pensar sobre su corrección alcanza con hacer induccion para demostrar que la función retorna la misma lista sin duplicados. Voy a hacer un esquema del razonamiento que nos llevaria a una demostracion.

Paso base

El paso base es que la lista esta vacia. En ese caso se retorna una lista vacia, como una lista vacia es una lista sin duplicados, no hay nada más que demostrar. El codigo que soporta este caso es:


	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} 

Paso Inductivo

Ahora tenemos que demostrar que si llamamos a la funcion con una lista con n elementos sin duplicados entonces llamando a la función con la lista con n+1 elementos tambien se retorna una lista sin duplicados.

Para razonar sobre esto alcanza pensar que en el caso en que se llama a la función con (n+1) elementos, se llega a la siguiente porción de codigo:


		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}

Analizemos los dos casos:

  • Si el valor (n+1) ya existe en la lista, se devuelve la lista hasta n. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y se devuelve esta, la lista que se devuelve en la llamado con n+1 elementos es así mismo una lista sin duplicados.
  • Si el valor (n+1) no existe en la lista, se devuelve la lista hasta n mas el elemento n+1. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y por asunción de caso el elemento nuevo no existe en la lista hasta n, la lista que se devuelve en la llamado con n+1 elementos es una lista sin duplicados.

Por exhaustación de casos, se comprueba que se cumple el paso inductivo.

Algunas observaciones sobre el algoritmo

El proximo paso y va ser el siguiente post es analizar la complejidad del algoritmo y despues buscar formas de mejorarlo. Como observaciones basicas se puede ver que llamando a la función sacar_duplicados() con una lista con n elementos, se itera (recursivamente) por cada uno de los n elementos de la lista, por otro lado la lista pasados va creciendo con cada llamado a esta_en_lista() que tiene un elemento nuevo y en todo caso de que este elemento sea mayor a cualquiera de los j elementos anteriores de pasados, esta_en_lista() itera por cada uno de los j elementos de pasados. Es pensando en estos temas que vamos a encarar el siguiente post.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Primera Solución

Iterando por una matriz cuadrada recursivamente

Icono de Post June 5 2009 :: Algoritmia, Estructuras de datos, Java, Lógica ::

En otro ejercicio de la facultad se me pedía sumar todos los valores individuales de una matriz cuadrada a través de un algoritmo recursivo. Mi resolución en Java fue la siguiente:


	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
			if(n > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b
			} else {	
				return arr2[m][n];
			}
		} else { //n > m
			if(m > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c
			} else {
				return arr2[m][n];
			}
		}
	}

Me interesa este ejercicio para pensar de otra forma sobre corrección de programas. La pregunta es si el algoritmo es correcto y después de pensarlo un poco llegue a la conclusión de que lo era. Por lo pronto para hacer una demostración formal debería usar inducción estructural pero este post trata más bien sobre trabajo previo a una demostración, lo que en How to Prove it llaman scratchwork. O sea el razonamiento a través del cual se llega a una demostración.

Primero que nada hagamos un poco de debugging con un caso simple de una matriz de 3x3. Para esto agregamos lo siguiente al código anterior:


	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		System.out.println(n + " " + m);
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
....
....

Y testeamos la función llamándola con:


public class TP4 {

	public static void main (String[] args) {
		int[][] arr2;
		arr2 = new int[3][3];
		arr2[0][0] = 1;
		arr2[0][1] = 2;
		arr2[0][2] = 2;
		arr2[1][0] = 4;
		arr2[1][1] = 2;
		arr2[1][2] = 3;
		arr2[2][0] = 4;
		arr2[2][1] = 7;
		arr2[2][2] = 8;
		System.out.println("Ej9:");
		System.out.println( TP4.sumaMatriz(arr2,2 ,2));
	}
}

Lo que muestra por consola es:


Ej9:

2 2
2 1
2 0
1 1
1 0
0 0
0 1
1 2
0 2

33

Podemos ver que todos los elementos de la matriz fueron accedidos y que el resultado es el correcto. Ahora imaginémonos el árbol de las llamadas de función.

Vemos que los elementos de la diagonal principal hacen 3 llamados más, al próximo elemento de la diagonal principal, y a los dos elementos con m o n decrementados en uno. Mientras que los elementos que no están en la diagonal principal hacen un solo llamado.

Razonamiento (Informal) sobre la corrección del Algoritmo

Consideremos una matriz cuadrada de grado m, tal que m sea mayor que 5 (esto es por claridad para hacer este ejercicio) y concentrémonos en los últimos 5x5 casilleros del limite inferior derecho, que es donde comienza el algoritmo.

Primer paso toma el elemento en m x m:

A partir de esto se realiza la llamada recursiva:


if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

De la que se desprenden los siguientes 3 pasos.

El caso b:


return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b

De nuevo el caso a:


if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

Y finalmente el caso c:


				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c

Hemos llegado a llenar una matriz de 3x3, pero esto no nos demuestra nada, ahora lo interesante es saber que pasa cuando continua el algoritmo en los pasos siguientes y aquí es donde esta el truco.

Lo interesante es que las 3 posibles llamadas recursivas garantizan la siguiente:

  • Por el caso a, desde una llamada de la función desde un casillero en la diagonal principal, no se llamara a la función en ningún casillero que este en la misma linea o columna de los elemento de donde han sido llamados por un casillero en la diagonal principal anterior.También por el caso a, la iteración a través de elementos de la diagonal principal eventualmente cubrirá todos los elementos de la diagonal principal de la matriz.

  • Por el caso b, desde una llamada de la función desde un casillero en una columna que no sea en la diagonal principal, siempre continuara por esa misma columna hasta completarla.

  • Por el caso c, desde una llamada de la función desde un casillero en la fila que no sea en la diagonal principal, siempre continuara por esa misma fila hasta completarla.

A partir de esto podemos inferir que el algoritmo pasa por todos los elementos de cualquier matriz cuadrada.

Importante

Quiero recalcar que esto es un razonamiento, a partir del cual por inducción estructural podría construirse una demostración, pero en términos de lógica formal no es una demostración. Igual, no deja de ser un razonamiento valido, lo cierto es que en la programación como practica es importante poder pensar si lo que se esta haciendo es correcto y si los programas que uno hace cumplen con las necesidades que uno tiene, pero también es cierto que sería completamente Overkill el tener que hacer una demostración formal de cada programa que uno hace. Lo importante es tener herramientas para poder razonar y pensar sobre como se programa.

Autor: Emiliano Martínez Luque.

Comments Off on Iterando por una matriz cuadrada recursivamente

Razonando sobre corrección de Programas en Haskell

Icono de Post May 18 2009 :: Algoritmia, Combinatoria, Haskell, Lógica ::

Una de las cosas más interesantes de Haskell es lo facil que resulta razonar sobre corrección de programas. Veamos un ejemplo simple; construiremos una función que tome 3 elementos ordenables y los devuelva como una triada ordenada (Ejercicio 2.40 de Razonando con Haskell):


ordena3:: Ord a => a -> a -> a -> (a, a, a )
ordena3 a b c 	| a <= b && b <= c = (a, b, c) 		-- Caso 1
	 	| a <= b = ordena3 a c b		-- Caso 2
		| b <= c = ordena3 b a c		-- Caso 3
		| otherwise = (c, b, a)			-- Caso 4

Las posibles permutaciones de un conjunto de 3 elementos distintos son obviamente 3! = 2 * 3 = 6. Sean 3 elementos ordenables distintos, a los que llamamos 1, 2, 3 tales que 1 < 2 < 3, veamos como trata el programa estas 6 permutaciones distintas:

ordena3 1 2 3 Caso 1 -> (1 ,2 ,3)
ordena3 1 3 2 Caso 2 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 2 1 3 Caso 3 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 2 3 1 Caso 2 -> ordena3 2 ,1 ,3; Caso 3 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 3 1 2 Caso 3 -> ordena3 1 ,3 ,2; Caso 2 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 3 2 1 Caso 4 -> (1 ,2 ,3)

Las condiciones exhaustuan todos los caso y el algoritmo termina siempre. ( No se consideran los casos en que existen elementos duplicados en la explicación ya que es trivial ver que por el uso de <= en las condiciones están contemplados en la definición de la función. )

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Autor: Emiliano Martínez Luque.

Comments Off on Razonando sobre corrección de Programas en Haskell

Ejercicio 4.7 de THRTLMP

Icono de Post September 10 2008 :: Lógica, Teoría de Conjuntos ::

Se nos pide demostrar que siendo A un conjunto de conjuntos, el conjunto { x ∈ A | x ∉ x } ∉ A. Es interesante y por eso lo blogueo porque es una aplicación de la paradoja de Russell.

Demostración

Llamemos B al conjunto { x ∈ A | x ∉ x }. Supongamos que B ∈ A y consideremos a B con respecto a si mismo desde la relación ∈, o bien B ∈ B o bien B∉ B.

Supongamos que B ∈ B entonces por la propia definición de B, B ∉ B, lo cual es una contradicción. Ahora si B ∉ B también por la definición de B sigue que B ∈ B, lo cual también es una contradicción.

Dado que nuestra premisa original nos lleva siempre a una contradicción, debe ser falsa, por consiguiente B ∉ A.

Es interesante también como este ejercicio sirve de introducción a los tipos y clases de Haskell.

Autor: Emiliano Martínez Luque.

Comments Off on Ejercicio 4.7 de THRTLMP

Una Demostración con Incognitas

Icono de Post September 6 2008 :: Lógica ::

Esta demostración maravillosa que esta en el ejercicio 3.7.9 del libro How to Prove It: A Structured Approach, que la transcribo directamente porque es fantástica.

Teorema: Existen 2 números Irracionales a,b tales que ab es racional.

Demostración: O ( 2 ) 2 es racional o es irracional.

Caso 1: Si es racional, ya se probo lo que queríamos probar porque 2 es irracional y tomamos a=b= 2 .

Caso 2: Si es irracional entonces sea a = ( 2 ) 2 y b = 2 . Entonces podemos formar el numero ( ( 2 ) 2 ) 2 = ( 2 ) 2 . 2 = ( 2 ) 2 = 2 . Como 2 es irracional, ( 2 ) 2 es irracional por asumción de caso y 2 es racional, el Teorema queda demostrado.

Lo maravilloso es que llegamos a una demostración rigurosa del teorema sin necesidad de saber si   ( 2 ) 2 es irracional o no. Simplemente por exhaustación de casos el teorema queda demostrado.
Nota: es irracional, lo que igual no quita lo maravilloso de la demostración y lo impecable de su lógica.

Autor: Emiliano Martínez Luque.

Comments Off on Una Demostración con Incognitas

Ejercicio 3.42 de THRTLMP

Icono de Post August 4 2008 :: Algebra, Lógica ::

Se nos pide demostrar si hay o no hay triplos de primos de la forma ( p , p+2, p+4 ) que no sean ( 3, 5, 7 ). Este ejercicio me gusto porque estuve unos 15 minutos pensando antes de poder resolverlo. Bueno, despues de mirar un poco la Criba de Eratosthenes y pensar en la aritmetica mod( 3 ) finalmente encontre la forma:

Demostración

Sabemos que p es primo por lo tanto no es multiplo de 3, o sea que es o de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p + 2 = 3k + 1 + 2 = 3 ( k + 1 ) entonces p + 2 es multiplo de 3 y no es primo. Ahora si es de la forma 3k + 2 entonces p + 4 = 3k + 2 + 4 = 3 ( k + 2) por lo que p + 4 es multiplo de 3 y no es primo. De lo que sigue que no existen triplos de primos de la forma ( p, p+2, p+4 ) salvo ( 3, 5, 7 ).

De manera similar puede resolverse el ejercicio 3.43, que es demostrar que siendo p primo, no existen primos de la forma ( p2 + 2 ) ≠ 11 o lo que es lo mismo con p ≠ 3 .

Demostración

Si p es primo ≠ 3 , entonces necesariamente no es multiplo de 3, o sea que es de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p2 + 2 = ( 9k2 + 6k + 1) + 2 = 3 ( 3k2 + 2k + 1 ) , porque lo que es multiplo de 3 y no es primo. Supongamos entonces que es de la forma 3k + 2, entonces p2 + 2 = ( 9k2 + 12k + 4) + 2 = 3 ( 3k2 + 4k + 2 ), multiplo de 3 y no primo. Por exhaustación de casos, la proposición queda demostarda.

Bueno termine con el cápitulo 3, si alguién tiene la solución del ejercicio 3.34 me haría un favor enorme si me lo mandan porque estuve un buen rato y no lo pude resolver. Mierda, me gustaría poder dedicarle más tiempo, pero si me cuelgo no avanzo más y quiero seguir aprendiendo Haskell.

Autor: Emiliano Martínez Luque.

Comments Off on Ejercicio 3.42 de THRTLMP

La inducción completa es un arma poderosa

Icono de Post August 4 2008 :: Algebra, Lógica ::

Resolución del ejercicio 3.41 de The Haskell Road To Logic, Math and Programming. Demostrar que 2n – 1

( 2n– 1 ) es un numéro perfecto ( la suma de todos sus divisores propios es igual al mismo número ) si ( 2n– 1 ) es primo ( un primo de mersenne en realidad ). Como es primo se puede descomponer en los siguientes divisores propios:

2n – 1

( 2n– 1 ) = 1 + 2 + 22 + …. + 2n – 1 + ( 2n– 1 ) + 2.( 2n-1 ) + 22.( 2n-1 ) + …. + 2n – 2.( 2n-1 )

= 1 + 2 + 22 + …. + 2n – 1 + ( 2n– 1 ) + ( 2n + 1 -2 ) + ( 2n + 2

– 22 ) + …. + ( 22n – 2

– 2n – 2)
Realizando las multiplicaciones de los terminos del final.

= 2n – 1
+ 2n + 2n + 1 +  2n + 2

+ …. + 22n – 2

Simplificando terminos equivalentes pero negativos.

= 2n – 1

( 1 + 2 + 22 + …. + 2n – 1 )
Por propiedades de la exponenciación.

= 2n – 1( 2  – 1 + 2 + 22 + …. + 2n – 1 )
Porque 2 – 1 = 1

Y es exactamente acá donde la cosa se pone interesante.  Ya logre 2n – 1 y el – 1 en el segundo termino. Pero me queda demostrar que ( 2 +2 + 22 + …. + 2n – 1 ) = 2n .

En principio no parece demasiado complicado.. digamos:

2 + 2 = 4 = 22

22 + 22 = 8 = 23

23 + 23 = 16 = 24

…….

2n – 1

+ 2n – 1 = 2n

Que se puede probar fácilmente por inducción completa.

2n = 2n – 1

+ 2n – 1

1) Demostrarlo para n = 1, es trivial: 2 = 1 +1.

2) 2n = 2n – 1
+ 2n – 1

=> 2n + 1
= 2n + 2n
2n + 2n = 2.(2n – 1

+ 2n – 1) = 2.2n (Por hipotesis) =  2n + 1

Ahora, en el texto todavía no vimos inducción y hay un capitulo entero dedicado al tema. El tema es como probar esto sin usar inducción completa. Ni la más puta idea.

DUH! Agregado ( 1 mes después releyendo mi post y sorprendiéndome por mi absoluta falta de lucidez al momento de escribirlo )

2n – 1 + 2n – 1 = 2. (2n – 1) = 2n

Autor: Emiliano Martínez Luque.

Comments Off on La inducción completa es un arma poderosa

Generalizando demostraciones

Icono de Post July 25 2008 :: Algebra, Lógica ::

En el ejercicio 3.21.12 del libro Algebra I de Armando Rojo, se nos pide demostrar por inducción completa que:

3 / 8n – 5n o lo que es lo mismo 8n – 5n = 3k; k ∈ Z .

Lo interesante es que cuando curse Algebra y Matematica Discreta había un ejercicio bastante similar ( Demostrar que 5 / 7n – 2n).  Se me ocurrio entonces que la demostración podía generalizarse.

Demostración Inicial: 3 / 8n – 5n

1) Primer paso demostrar para n=1

3 / 8 -5 => 3 / 3
Lo cual es evidentemente cierto.

2) Paso Inductivo:
8n – 5n = 3k; k ∈ Z => 8n+1

– 5n+1
= 3w; w ∈ Z

Demostración:

3 / 8n+1

– 5n+1
=> 8n+1

– 5n+1
= 3k; k ∈ Z

8n+1

– 5n+1
= 8 . 8n – 5 . 5n
Por Propiedades de la exponenciación.

= ( 3 + 5 ). 8n – 5 . 5n    
Porque 8 = 3 + 5.

= 3 .8n + 5. 8n + – 5 . 5n
Por distributividad.

= 3 .8n + 5. ( 8n – 5n )
Por dirtributividad.

= 3 .8n + 5. ( 3.k )
Por hipotesis.

= 3 ( 8n + 5k )    
Por Distributividad:

Como ( 8n + 5k ) ∈ Z ; queda demostrada la proposición inicial.

Demostración generalizada: Sean a,b,c ∈ Z; a = b -c se cumple que a / bn – cn

1) Primer paso demostrar para n=1

b1 – c1

= a         (Por Definicion de a,b,c)

2) Paso Inductivo:
bn – cn = ak; k ∈ Z => bn+1

– cn+1
= aw; w ∈ Z

Demostración:

a / bn+1

– cn+1
=> bn+1
– cn+1

= ak; k ∈ Z

bn+1
– cn+1
= b . bn – c . cn
Por Propiedades de la exponenciación.

= ( a + c ). bn – c . cn
Porque a = b – c => b = a + c

=  a. bn + c .bn – c . cn
Por distributividad.

= a .bn + c. ( bn – cn )
Por dirtributividad

= a .bn + c. ( a.k )
Por hipotesis.

= a ( bn + ck )
Por Distributividad.

Como ( bn + ck ) ∈ Z queda demostrada la proposición.

Referencias

Algebra I; Rojo, Armando; 21ª ed, Magister Eos; 2006

Autor: Emiliano Martínez Luque.

Comments Off on Generalizando demostraciones

Un ejemplo de Inducción Completa sobre N

Icono de Post July 25 2008 :: Lógica ::

Hace unos días me encontre en el medio de una demostración sobre propiedades de los limites con la siguiente formula:

1 – qn = ( 1 – q ) ( 1 + q1 + q2 + …. + qn-1)

Lo interesante es que lo daba como un hecho ya establecido. Como nunca me habia encontrado con esa formula, decidi investigarla un poco. En principio, parece bastante lógico, ya que si multiplicamos en el segundo termino 1 por la seguna secuencia nos queda una serie de terminos positivos  1 + q + q2 + …. + qn-1
  y al multiplicar el -q por la segunda secuencia nos queda  -q  – q2 – q3  …. – qn . Con lo cual salvo el primer 1 y el ultimo – qn todo el resto de los terminos se anulan entre si. Ej:

( 1 – q ) ( 1 + q + q2 + …. + qn-1) = ( 1 + q1 + q2 + …. + qn-1) + ( – q1  – q2 … – qn-1

–  qn) = 1 + q1 – q1 + q2 – q2 + …. + qn-1 – qn-1

–  qn  =  1 – qn

Esa es una buena explicación, pero sin embargo la propiedad ( así como estaba formulada ) no se cumple para n=1:

( 1 – q ) .(1 + qn-1) = ( 1 – q ) ( 2 ) =  2 -2q ≠ ( 1 – q1)

Entonces habría que reformular la propiedad:

∀n ϵ N, n > 2:  1 – qn = ( 1 – q ) ( 1 + q + q2 + …. + qn-1 )

Y la demostración por Inducción Completa sería:

1) Primer paso, probarlo para n = 2.

1 – q2 = ( 1 – q ) ( 1  + qn-1 )  = ( 1 + q) + ( – q – q2 ) = ( 1 – q2 )

2) Paso inductivo:.

1 – qn+1 = ( 1 – q ) ( 1 + q1 + q2 + …. + qn-1 + qn)

Por multiplicación entre polinomios queda:

= ( 1 + q1 + q2 + …. + qn-1 + qn ) + ( – q1  – q2 … – qn-1 –  qn –  qn+1)

Por conmutatividad de + en R:
= ( 1 + q1 + q2 + …. + qn-1 ) + ( – q1  – q2 … – qn-1

–  qn ) + qn –  qn+1
  

Por hipotesis queda:

= (1 – qn) + qn –  qn+1

Simplicando las sumas y restas queda:

= 1 –  qn+1

Con lo cual queda demostrada la propiedad.  

Nota: Es interesante pensar que teniendo en cuenta que  ∀ q ∈ R: q0= 1 , si se reformula la propiedad de la siguiente forma :

1 – qn = ( q0 + q1 + q2 + …. + qn-1 )

Si se cumple para n = 1 .

Autor: Emiliano Martínez Luque.

Comments Off on Un ejemplo de Inducción Completa sobre N