Matlab Uch1 Clase10

MATEMÁTICA DISCRETA Clase 10 •PRINCIPIO DEL PALOMAR

El nombre de Gustav Dirichlet (1805- 59) aparece ligado amuchos campos de las Matemáticas y de la Física. Sucedió a K. F. Gauss en la cátedra de la prestigiosa universidad alemana de Gotinga, uno de los centros matemáticos más prestigiosos del siglo XIX y de comienzos del XX. 1

Principio del Palomar Si |A| > |B| entonces ninguna f : A → B es inyectiva. En lenguaje más sencillo esto equivale a decir que si n objetos se distribuyen en k cajas y n > k entonces alguna caja recibe más de un objeto. El nombre Principio del palomar proviene de que si hay más palomas que nidos en un palomar y cada paloma entra en un nido, entonces algún nido contendrá más de una paloma. Este principio también se conoce como principio de las cajas o de las casillas.

Universidad de Ciencias y Humanidades Algebra Computacional

2

Ejemplo 1. Si en una sala hay 13 o más personas, entonces existe un par (quizá más) de personas cuyo cumpleaños cae el mismo mes. Es relativamente simple darse cuenta que lo anterior es cierto, pues como un año tiene 12 meses y hay más personas que meses, por obligación en algún mes estarán de cumpleaños 2 o más personas. Ejemplo 2. En cualquier conjunto de tres personas hay dos del mismo sexo. Ejemplo 3. En cualquier conjunto de trece personas hay dos nacidas en el mismo mes.

Universidad de Ciencias y Humanidades Algebra Computacional

3

PROBLEMAS RESUELTOS Problema 1 Probar que si se escogen 26 números naturales diferentes, impares y menores que 100, siempre hay dos de ellos que suman 100. Solución Hay 25 pares de números impares diferentes entre 1 y 99 que suman 100, a saber {1, 99}, {3, 97}, {5, 95},. . . , {49, 51}. Dados 26 números impares diferentes entre 1 y 99, cada uno de ellos pertenece a uno de los 25 pares. Por el principio del palomar debe haber dos números pertenecientes a un mismo par, y que por lo tanto suman 100.

Universidad de Ciencias y Humanidades Algebra Computacional

4

Problema 2. En un estadio hay 10, 000 personas. Demostrar que hay al menos un grupo de 28 personas que está de cumpleaños el mismo día. Solución. Bastaría considerar a las personas del estadio como nuestros “objetos” y a los días del año como nuestros “casilleros” (podemos “clasificar” a las personas según su día de cumpleaños). Así, tenemos que el número de personas es n = 10000 y el número de días del año es k = 366 (consideramos el caso fortuito de que haya personas nacidas en días 29 de febrero). Podemos notar, además, que 366×27 = 9882, entonces 10000 > 27×366 (es decir, k = 27), luego, el Principio del Palomar nos asegura que en alguno de los días del año hay 28 o más personas de cumpleaños. Universidad de Ciencias y Humanidades Algebra Computacional

5

Problema 3. ¿Cuántas veces, como mínimo, debe lanzarse un par de dados para asegurarse que el puntaje obtenido (la suma de los dados) se repita? Solución. Ahora el objetivo es otro, es asegurarse que haya dos dados (resultados) que se repitan minimizando el número de objetos. Para ello basta simplemente contar el número de resultados posibles. Con dos dados uno puede obtener números desde el 2 hasta el 12, es decir, 11 resultados distintos. Si sólo tiráramos los dados 11 veces entonces podría suceder que en cada tirada obtuviéramos un resultado distinto. Si tiramos, en cambio, 12 veces los dados, como 12 es mayor que 11, el Principio del Palomar nos asegura que al menos en dos ocasiones obtendremos el mismo resultado. Luego, el número mínimo de veces que han de lanzarse los dados para estar seguro es 12. Universidad de Ciencias y Humanidades Algebra Computacional

6

EJERCICIOS COMPLEMENTARIOS 1) Si se dibuja un triángulo equilátero de dos centímetros de lado y se eligen cinco puntos situados dentro del triángulo, al menos dos de ellos distan entre sí más de un centímetro. 2) Si del conjunto de números 1, 2, 3, 4, 5, 6, 7 ,8, 9 y 10 seleccionamos seis, habrá, con seguridad, dos números que sumen 11. 3) A un campo de fútbol han acudido 20.000 espectadores, ¿cuántos de ellos, como mínimo, cumplen años el mismo día? 4) Demostrar que si repartimos cien canicas en catorce grupos, tiene que haber dos grupos con el mismo número de canicas. 5) Si elegimos veinte números naturales cualesquiera, hay siempre dos, por lo menos, cuya diferencia es múltiplo de 19.

Universidad de Ciencias y Humanidades Algebra Computacional

7

6) Demuestra que dados cinco puntos cualesquiera en un cuadrado de lado 2 hay al menos dos puntos que distan como mucho 2. ¿Es verdad para 4 puntos? 7) Los estudiantes de una clase tienen el pelo negro, marrón, rojo, blanco o azul. Hay 101 estudiantes en clase. Probar que al menos hay 21 estudiantes que tienen el pelo del mismo color. (Aquí los nidos son los colores y las palomas son los estudiantes).

Universidad de Ciencias y Humanidades Algebra Computacional

8