Matematica discretas

Solo disponible en BuenasTareas
  • Páginas : 5 (1230 palabras )
  • Descarga(s) : 0
  • Publicado : 12 de enero de 2010
Leer documento completo
Vista previa del texto
Principio de Dirichlet o principio del palomar
¿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? ¿Ysi 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, perosó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 posibleentre 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 33móviles de cada tipo, pues como 60×33=1980, en cuanto tengamos más de 1980 móviles, tiene que haber al menos un tipo del que haya más de 33 móviles, pues si no habría más de 60 tipos.

El 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 yb=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 estoscá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 escribirel 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 unmismo 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...
tracking img