apellidos Olmos, Pérez, Quintana y Rodríguez. Demuestre que al
menos dos personas tienen el mismo nombre y apellido.
2. Dieciocho personas tienen nombres de pila Alfredo, Benjamín y
César y apellidos Domínguez y Enríquez. Demuestre que al menos
tres personas tienen el mismo nombre y apellido.
3. La profesora Eugenia recibe su salario todos los viernes. Demuestre
que en algunos meses le pagan tres veces.
4. ¿Es posible interconectar cinco procesadores de manera que exactamente
dos de ellos tengan conexión directa a un número idéntico
de procesadores? Explique su respuesta.
5. Un inventario consiste en una lista de 115 artículos, cada uno marcado
como “disponible” o “no disponible”. Hay 60 artículos disponibles.
Demuestre que hay al menos 2 artículos disponibles en
la lista que están separados por exactamente 4 artículos.
6. Un inventario consiste en una lista de 100 artículos, cada uno marcado
como “disponible” o “no disponible”. Hay 55 artículos disponibles.
Demuestre que hay al menos dos artículos disponibles
en la lista que están separados por exactamente 9 artículos.
7. Un inventario consiste en una lista de 80 artículos, cada uno marcado
como “disponible” o “no disponible”. Hay 50 artículos disponibles.
Demuestre que hay al menos 2 artículos no disponibles
en la lista que están separados por 3 o por 6 artículos.
8. Complete el ejemplo 6.8.5 demostrando que si los pares (P1, Pi),
(P1, Pj), (P1, Pk) son no similares, hay tres fotografías que son mutuamente
similares o mutuamente no similares.
9. ¿Se puede afirmar necesariamente la conclusión del ejemplo 6.8.5
si hay menos de 6 fotografías? Explique por qué.
10. ¿Se puede afirmar necesariamente la conclusión del ejemplo 6.8.5
si hay más de 6 fotografías? Explique por qué.
En los ejercicios 11 al 14 dé un argumento que muestre que si X es cualquier
subconjunto de (n + 2) elementos del conjunto {1, 2, . . . ,2n + 1} y m es el elemento más grande en X, existen i y j distintos en X con m = i + j.
Para cada elemento k ∈ X − {m}, sea
11. ¿Cuántos elementos hay en el dominio de a?
alguna i j.
14. Explique por qué el ejercicio 13 implica que existen i y j distintos
en X con m = i + j.
15. Dé un ejemplo de un subconjunto X de (n + 1) elementos del conjunto
{1, 2, . . . , 2n + 1} que tenga la propiedad: no hay dos elementos
distintos i, j ∈ X para los que i + j ∈ X.
En los ejercicios 16 al 19 dé un argumento que pruebe el siguiente resultado:
Una sucesión a1, a2, . . . , an2+1 de n2 + 1 números diferentes contiene
ya sea una subsucesión creciente de longitud n + 1 o bien una
subsucesión decreciente de longitud n + 1.
Suponga, a manera de contradicción, que toda subsucesión creciente
o decreciente tiene longitud n o menor. Sea bi la longitud de la
subsucesión creciente más larga que comienza en ai, y sea ci la longitud
de la subsucesión decreciente más larga que comienza en ai.
16. Demuestre que los pares ordenados (bi, ci), i = 1, . . . , n2 + 1, son
distintos.
17. ¿Cuántos pares ordenados (bi, ci) hay?
18. Explique por qué 1 ≤ bi≤ n y 1 ≤ ci≤ n.
En los ejercicios 20 al 23 dé un argumento que demuestre que en un
grupo de 10 personas hay al menos dos tales que la diferencia o la suma
de sus edades es divisible entre 16. Suponga que las edades están
dadas en números enteros.
Sean a1, . . . , a10 las edades. Sea ri = ai mod 16 y sea
20. Demuestre que s1, . . . , s10 tienen valores que van de 0 a 8.
21. Explique por qué sj= sk para alguna j k.
22. Suponga que sj= sk para alguna j k. Explique por qué si sj= rj y sk= rk o sj= 16 − rj y sk= 16 − rk, entonces 16 divide a aj− ak.
23. Demuestre que si las condiciones en el ejercicio 22 no se cumplen,entonces 16 divide a aj+ ak.
24. Demuestre que en la expansión decimal del cociente de dos enteros,
en algún momento un bloque de dígitos se repite. Ejemplos:
del 1 al 12, están colocados alrededor del cuadro central de la cancha
con un arreglo arbitrario. Demuestre que para algunos tres jugadores
consecutivos, la suma de sus números es al menos 20.
26. Para la situación del ejercicio 25, encuentre y pruebe una estimación
de qué tan grande debe ser la suma de los números para algunos
cuatro jugadores consecutivos.
27. Sea f una función uno a uno de X = {1, 2, . . . , n} sobre X. Sea f k = f f · · ·
f la composición de f, k veces consigo misma.
Demuestre que existen enteros positivos diferentes i y j tales que
f i(x) = f j(x) para toda x ∈ X. Demuestre que para algún entero positivo
k, f k(x) = x para toda x ∈ X.
28. Un rectángulo de 3 × 7 se divide en 21 cuadrados cada uno coloreado
rojo o negro. Pruebe que el tablero contiene un rectángulo
no trivial (no 1 × k o k × 1) cuyos cuatro cuadrados en las esquinas
son todos negros o todos rojos.
29. Pruebe que si p unos y q ceros se colocan alrededor de un círculo
de manera arbitraria, donde p, q y k son enteros positivos que satisfacen
p ≥ kq, el arreglo debe contener al menos k unos consecutivos.
30. Escriba un algoritmo que, dada una sucesión a, encuentre la longitud
de la subsucesión creciente de a más larga.
31. Una rejilla de 2k × 2k se divide en 4k2 cuadrados y cuatro subrejillas
de k × k. La figura siguiente muestra la rejilla para k = 4:
Demuestre que es imposible marcar k cuadrados en la subrejilla de k ×
k superior izquierda, y k cuadrados en la subrejilla de k × k inferior derecha,
de manera que no haya dos cuadros marcados en el mismo renglón,
columna o diagonal de la rejilla de 2k × 2k.
Ésta es una variante del problema de las n reinas que se analiza
con detalle en la sección 9.3.
