Republica De Venezuela

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Educación Universitaria

Universidad Politécnica Territorial del Estado Aragua

Extensión Maracay

TRABAJO DE MATEMATICA

INTEGRANTES:

Secc. 2

INFORMÁTICA

Maracay, FEBRERO de 2014

INTRODUCCION

Hoy en día vemos cosas que nos pueden parecer de lo más cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas más; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.

En este trabajo se tratará brevemente de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así como en la memoria especificado detalladamente en ejemplos.

En este trabajo, tratamos de ser lo más breves posible explicando de manera muy sencilla los conceptos y algunas metodologías con un lenguaje no tan rebuscado para su mayor entendimiento.

Dada esta pequeña introducción empezará el desarrollo del tema.

Principio de Dirichlet o principio del Palomar

El principio del palomar, también llamado principio de Dirichlet, dice que, “si hay n huecos en un palomar, y n+1 palomas, entonces hay al menos un hueco en el que viven al menos dos palomas”. Este resultado se puede generalizar de la siguiente forma: si hay k conjuntos, y N elementos distribuidos en dichos conjuntos, donde podemos escribir N=a×k+b, siendo a un entero no negativo y b uno de los números (1,2,3,...,k), entonces hay al menos un conjunto que tiene al menos a+1 elementos. En el caso anterior, teníamos 60 conjuntos (tipos de móviles), 2010 elementos (móviles), con lo que a=33 y b=30, y tenemos al menos un tipo del que hay al menos a+1=34 móviles. Vemos ahora otro par de ejemplos, en los que hay que “preparar el terreno” antes de aplicar el principio del palomar. Normalmente, esto suele requerir, bien calcular el número de conjuntos, bien calcular el número de elementos que necesitamos en cada conjunto, bien el número total de elementos, bien una combinación de estos cálculos.

Ejemplo 1: ¿Cuántos números que sean cuadrados perfectos (es decir, que sean el resultado de elevar al cuadrado un entero) necesito como mínimo, para garantizar que hay al menos dos de ellos cuya diferencia es múltiplo de 5?

Solución: si divido un número entero cualquiera entre 5, puedo obtener un cociente entero c, y un resto r que puede tomar valores 0, 1, 2, 3 o 4, pudiendo escribir el número como 5c+r. Si elevo al cuadrado, obtengo 5(5c2+2cr)+r2. Como r2 puede tomar valores 0, 1, 4, 9, o 16, el resto al dividir (5c+r)2 entre 5 sólo puede ser igual a 0 (si r=0), 1 (si r=1 o 4) o 4 (si r=2 o 3). La diferencia entre dos números es múltiplo de 5, si y sólo si tienen el mismo resto al dividir entre 5, es decir, lo que me piden es que garantice que hay al menos dos elementos en un mismo conjunto, de entre tres conjuntos posibles de restos al dividir por 5 que puede tener un cuadrado perfecto. El principio del palomar me garantiza que eso es cierto en cuanto hay 4 elementos distintos, y si tengo como máximo 3 elementos, puedo distribuirlos hasta tener como mucho uno en cada conjunto (por ejemplo 1, 4 y 25). Luego tomando 4 cuadrados perfectos, puedo garantizar que la diferencia entre dos de ellos va a ser múltiplo de 5, pero no con menos.

Ejemplo 2: dibujamos en el plano un hexágono regular de lado 3 metros, y pintamos en su interior o en su frontera 2009 puntos rojos distintos. Demuestra que hay un triángulo equilátero de lado 1 metro, incluido en el interior o la frontera del anterior, en cuyo interior o frontera hay al menos 38 puntos rojos distintos.

Solución: podemos dividir el hexágono regular en tres triángulos equiláteros de lado 3 metros, dibujando sus diagonales mayores. Cada uno de estos triángulos puede ser a su vez dividido en 9 triángulos equiláteros de lado 1 metro, dividiendo primero cada lado en tres segmentos iguales, y luego dibujando por cada uno de los puntos de división líneas paralelas a los lados del triángulo (¡prueba tú mismo a hacer el dibujo!). Tenemos así el hexágono dividido en 54 triángulos equiláteros de lado 1 metro, de forma que los interiores y las fronteras de estos triángulos cubren completamente el interior y la frontera del hexágono. Como 2009=54×37+11, y cada punto rojo, al estar en el hexágono, está en uno de los 54 triángulos, entonces por el principio del palomar hay al menos uno de los triángulos que contiene al menos 38 puntos.

¿Hay dos Iguales?

60 personas están comparando sus móviles (cada persona tiene exactamente un móvil). Hay móviles de 4 fabricantes distintos, y cada fabricante produce 5 modelos distintos. Además, cada modelo puede tener cámara y bluetooth, tener sólo bluetooth, o no tener ni bluetooth ni cámara. ¿Podemos garantizar que hay dos móviles iguales? ¿Y si en vez de 60 personas son 61?

Hay 4 posibilidades para fabricante, 5 para modelo, y 3 para complementos, para un total de 60 posibles tipos distintos de móviles. Si hay exactamente 60 móviles, pueden ser cada uno de un tipo, y no podemos garantizar que hay dos iguales. Si hay 61 móviles, tiene que haber necesariamente dos iguales, pues si fueran todos distintos, habría 61 tipos de móvil, pero sólo hay 60.

¿Cuántos Iguales hay?

Supongamos ahora que, con los mismos tipos de móviles que en el caso anterior, hay 2009 personas. Buscamos el tipo del que más móviles hay iguales. ¿Cuál es el máximo número de móviles de dicho tipo que podemos garantizar que haya?

Conseguiremos que haya un número mínimo de móviles en cada tipo cuando distribuyamos los móviles de la forma más equilibrada posible entre los 60 tipos distintos. Así, como 2009=60×33+29, podemos en principio tomar 33 móviles de un mismo tipo, para 30 tipos distintos, y 34 móviles de un mismo tipo, para otros 30 tipos distintos, para un total de

34 × 29 + 33 × 31 = 986 + 1023 = 2009 móviles.

No podemos entonces garantizar que haya más de 34 móviles iguales de cualquier tipo. Sí podemos garantizar que va a haber más de 33 móviles de cada tipo,

...