Download Olimpiada Costarricense de Matemáticas Elaborado por Luis

OLCOMA
Capítulo II: Lógica
Olimpiada Costarricense de Matemáticas
Elaborado por Luis Gómez Rodríguez
Material para capacitación de estudiantes
Olimpiadas Costarricenses de Matemática
NIVEL A
Tema: Lógica
2012
Olimpíadas Costarricenses de Matemática
1
OLCOMA
Capítulo II: Lógica
Resolución de Problemas (Lógica)
A. Problemas Introductorios
1.
Si el mejor reloj es que da la hora correcta con mayor frecuencia y alguien tiene dos relojes, uno que no funciona y otro que
atrasa un minuto por día. ¿Cuál es el mejor reloj?
2.
100 personas constestaron un cuestionario compuesto por tres preguntas. Cada pregunta debía constestarse por sí o por no,
y una sola de estas respuestas era correcta. Si sabemos que:
8 personas contestaron bien las tres preguntas
9 personas contestaron bien sólo la primera y la segunda.
11 personas contestaron bien sólo la primera y la tercera
6 personas contestaron bien sólo la segunda y la tercera
55 personas contestaron bien, por lo menos la primera pregunta.
32 personas contestaron bien, por lo menos la segunda pregunta.
49 personas contestaron bien, por lo menos la tercera pregunra
¿Cuántas personas no contestaron ninguna pregunta correcta?
3.
El 70% de los habitantes de un país habla un idioma y el 60% de la misma población habla otro idioma. ¿Qué porcentaje de la
población habla los dos idiomas, sabiendo que cada habitante habla al menos uno de ellos?
4.
Juan compró dos radios y después los vendió a ¢5000. En uno de los radio ganó un 15% y en el otro perdió un 15%. ¿De
cuánto fue la ganancia o pérdida de Juan?
5.
Si una gallina pone tres huevos en tres días, ¿Cuántos días se necesitan para que 4 gallinas pongan 2 docenas de huevos?
6.
Si el producto de 5 números es un número impar, ¿Cuántos de ellos deben ser impares?
7.
El resultado de
8.
El dígito número 2005 después de la coma en la expansión decimal de
9.
Si la base de un triángulo aumenta 10% y la altura disminuye un 10%. ¿Qué pasa con el área?
0.42 − 2.36 es
7
54
es:
10. La cabeza de un pescado tiene 30cm de largo, la cola es tan grande como la cabeza y la midar del cuerpo y el cuerpo es tan
largo como la cabeza y la cola juntas. ¿Cuál es la longitud del pescado?
11. En la siguiente figura, las distancias horizontales y verticales entre puntos consecutivos es de 1cm. ¿Cuál es el área del
triángulo?
2
Olimpíadas Costarricenses de Matemática
OLCOMA
Capítulo II: Lógica
12. ¿Cuánto suman los ángulos marcados en la figura?
13. Un enfermo toma una aspirina cada media hora. ¿En cuánto tiempo tomará cuatro aspirinas?
14. Si x barcos necesitan x días para consumir x tanques de aceite. ¿Cuántos días necesitan y barcos para consumir y tanques de
aceite?
15. Una persona sabe un secreto y se lo cuenta a 12 personas, asu vez cada una de estas doce se lo comunica a otras 12 y cada
una de estas a otras 12. ¿Cuántas personas saben el secreto?
16. Cuáles parejas de enteros (a,b) cumplen
0<b<8
y
a
a +1
+1 =
?
b
b +1
17. Miro el reloj. A partir de este momento el horario va a tardar justo el doble de tiempo que el minutero en llegar a las doce. ¿Qué
hora es?
18. En un campeonato de fútbol intervinieron 5 equipos, y cad equipo se enfrentó una vez a cada una de las escuadras
adversarias. Se asignó 2 puntos al ganador de un partido, 0 al perdedor y un punto, por empate. Los puntajes de cuatro de los
rquipos son:
PIERNAS LARGAS: 5puntos
MANOS FLOJAS:
3puntos
PONTE MOSCA:
6puntos
OLIMPICO:
1punto
¿Cuál es el puntaje de ATLETICO POCITOS?
Olimpíadas Costarricenses de Matemática
3
OLCOMA
Capítulo II: Lógica
B. Tácticas para Resolver Problemas
Cuando uno se enfrenta a un problema desconocido, surge uno de los principales conflictos de las olimpíadas:
¿Por dónde empiezo? La idea de este capítulo es dar algunas de las estrategias que un buen olímpico debe conocer
antes de competir en una olimpiada, que puede determinar el futuro de su carrera.
En el momento de resolver algún problema, sea en un entrenamiento o en una olimpiada, existen varios
métodos de entrarle al problema. Muchos de ellos son algo intuitivos, sin embargo hay otros que consisten en
esquematizar nuestra forma de pensar.
A continuación se describen algunas formas de cómo se pueden resolver los problemas:
Buscar un Patrón
Esta idea se utiliza sobre todo cuando estamos intentando resolver un juego o algún problema que involucre
varios casos. Aquí el truco es descubrir que todos los casos o algunos siguen un patrón específico, es decir se
comportan similarmente. Luego a partir de ese patrón que representa a varios de los casos podemos deducir algunas
propiedades interesantes.
Dibujar una figura
Esta técnica se usa sobre todo cuando nos enfrentamos a un problema de geometría o algún juego particular.
Ahora una cuestión importante es mencionar, que una figura no sustituye un enunciado geométrico, pero es una
buena ayuda para darnos ciertas pistas en la resolución del problema (es decir, la figura es sólo una guía, pero no es
el problema en sí). El truco de hacer una figura es que, muchas veces, nos clarifica el problema.
Dividir en casos
Esta técnica es fundamental. Muchos problemas parecen muy pesados, pero cuando se dividen en casos, el
problema puede hacerse más fácil. Ahora hay que garantizarse que la unión de todos esos casos nos del problema
original. Utilizaremos esta técnica junto con otras en este capítulo.
Aprovecharse de la simetría:
Existe una gran cantidad de problemas que son simétricos (cuando se menciona el término simetría, uno se
refiere a que hay un elemento central y a partir de allí los otros elementos se distribuyen de la misma manera con
respecto a ese centro; el ejemplo más común en el caso de la simetría es cuando uno se mira al espejo, que es el
elemento central, y observa que uno y la imagen de uno son simétricos con respecto al espejo). Así cuando
encontramos algún problema que tenga cierta simetría, podemos solamente concentrarnos en unos de los pedacitos
que es simétrico y así resolver para todos los demás el problema. En la siguiente sección veremos un problema al
respecto.
4
Olimpíadas Costarricenses de Matemática
OLCOMA
Capítulo II: Lógica
Seguir la paridad
Algunos problemas son muy fáciles de resolver si uno considera la paridad de algunos elementos..
Recordemos que si n es un número par lo podemos escribir de la forma n = 2⋅k, donde k es un número entero. Si n
es un número impar lo podemos escribir de la forma n = 2⋅k+1
Como veremos en los siguientes párrafos, el análisis de la paridad en una situación puede ser muy
beneficioso en la solución de problemas.
Escoger una notación efectiva
En varios problemas es bueno cambiar la notación Esto además de clarificar el problema puede hacer menos
tedioso, en algunos casos, su resolución. Debe buscarse notación que nos diga un poquita más de los que vemos a
simple vista.
Trabajar al revés:
Esta es una de las estrategias más importantes. Cuando a uno le piden resolver un problema, uno siempre
debe tener claro adonde quiere llegar. Y en algunos casos uno puede trabajar desde allí, el final, y encontrarse en el
principio. Es importante tomar en cuenta que hay pasos en los que uno se puede devolver y en los que no. Por
ejemplo, de
x=2 se sigue que x²=4, pero no nos podemos devolver ya que si x²=4 no necesariamente x=2. De ahí
que cuando trabajamos para atrás hay que tener cuidado para saber si uno se puede devolver o no. La gente que
acostumbra utilizar la estrategia de trabajar para atrás, le llama cocina.
Argumentar por contradicción:
Esta técnica consiste en el principio de negar lo contrario. Así si a uno le exigen demostrar una cosa, uno
puede demostrar que lo contrario es falso. La pregunta es qué es lo contrario y como expresarlo de manera adecuada.
Formular un problema equivalente:
Esta estrategia es muy importante, dado que muchas veces nos piden resolver un problema, pero podemos
resolver otro que es equivalente (cuando se habla de equivalente, quiere decir que resolver uno de ellos implica
resolver el otro). Así pues muchas veces no sólo hay que pensar en el problema sino también en los equivalentes que
conozcamos.
Modificar el problema:
En la mayoría de los problemas es recomendable modificar el problema. Ahora, cuando hablamos de
modificar el problema, nos referimos a cambiar algunos asuntos del enunciado, sin que esto afecte a la naturaleza del
mismo y así obtenemos un problema equivalente, que tal vez es más sencillo de resolver.
Olimpíadas Costarricenses de Matemática
5
OLCOMA
Capítulo II: Lógica
Considerar los casos extremos:
Esta estrategia consiste en analizar el mejor o el peor caso. Así si a uno le piden demostrar algunos casos,
basta, en muchas ocasiones analizar el caso extremo (mejor o peor) y a partir de allí deducir que si cierta propiedad
se cumple para el caso extremo, se cumplirá sin temor para los demás casos.
Generalizar:
Esta es la técnica más pesada, pero es bueno conocerla. Cuando hablamos de generalizar estamos diciendo
que una propiedad se cumple para ciertos elementos. En algunas ocasiones nos piden demostrar que cierta
característica la cumple un elemento. Bien, si uno demuestra que esa característica la cumplen todos los elementos,
en particular la cumplirá ese elemento original. Por ejemplo si nos pidiesen demostrar que Pepito no mide más de dos
metros de altura, bastaría con demostrar que ningún tico mide más que 2 metros y de allí se deduce lo primero.
Bien, después de haber hecho un recorrido por las diferentes formas de atacar un problema, es muy
importante recordar que dentro de la completa solución de un ejercicio existen tres pasos básicos: entenderlo,
resolverlo y redactarlo. Lo más increíble de todo es que se necesitan estos tres componentes, y no menos, para poder
demostrar que resolvimos el problema.
C. Problemas Resueltos
EJEMPLO 1.
Encuentra números enteros positivos
producto
n y a1 , a2 ,… an tales que a1 + a2 + … an = 1000 y el
a1 ⋅ a2 ⋅ … ⋅ an sea el mayor posible.
De entrada este problema parece complicado, pues 1000 se puede descomponer como una suma de muchas
maneras y entonces ¿cuál de estas será la que el producto es mayor?. Así a la hora de resolver este tipo de
problemas es bueno preguntarse que tiene en particular el número 1000 en este problema. La respuesta como
verás es simplemente un número para hacer complicado el análisis. Debemos, entonces intentar el problema
cambiando 1000 por números más manejables como 2,3,4,K. De esta manera te darás cuenta que el máximo
producto se obtiene cuando:
i.
Ningún ai debe ser mayor que 4
ii.
Ningún ai es igual a 1
iii.
Todos los ai son iguales a 2 ó 3.
iv.
A lo sumo hay dos 2 (porque 2·2·2<3·3 y 2+2+2=3+3)
Es preciso que verifiques esas afirmaciones y concluyas que la respuesta al problema original es 3
332
2
·2 .
Ejercicios:
1.
Si un conjunto tiene n elementos ¿Cuántos subconjuntos distintos tiene?
2.
(VI OIM) Para cada entero positivo
6
n
sea
an el último dígito del número 1 + 2 +…+ n .
Olimpíadas Costarricenses de Matemática
Calcular
a1 + a2 +…+ a1992
OLCOMA
EJEMPLO 2.
Capítulo II: Lógica
En un tablero de ajedrez, un caballo empieza en una determinada casilla y después de un
cierto número de movidas reglamentarias vuelve a la misma casilla. Muestre que el caballo
hizo un número par de movidas.
Imaginemos un tablero de ajedrez y supongamos que el caballo empezó en una casilla de color negro. En ese
caso, a la primer movida estará en un casilla blanca. Después de la segunda movida estará en una casilla negra.
A la siguiente movida estará de nuevo en una casilla blanca. Siguiendo este proceso nos damos cuenta de que si
se mueve un número impar de veces cae en una casilla blanca y si se mueve un número par de veces cae una
casilla negra. Por lo tanto, si vuelve a la casilla donde empezó realizó un número par de movimientos. El análisis
en el caso de que la casilla donde inició es de color blanco es exactamente igual.
EJEMPLO 3.
¿Podrá un caballo empezar en la casilla A1 y terminar en la casilla H8 pasando por cada una
de las otras casillas exactamente una vez?
No, no puede. Después de cada movida, el caballo brinca de un color a otro. Como el caballo debe de hacer 63
movidas, la última movida impar es impar y debe de caer en una casilla de color opuesto. Sin embargo, las
casillas A1 y H8 tienen el mismo color es imposible realizar lo que se desea.
EJEMPLO 4.
¿Se podrán escoger cinco números impares que sumen 100?
No y veamos por qué. Si sumamos dos números impares suma es un número par. Si a esto le sumamos un
número impar el resultado será impar. Podemos ver que la suma de una cantidad par de números impares da un
número par y la suma de una cantidad impar de números impares da un número impar. Este resultado es de
mucha importancia y nos permite ver que la suma de 5 números impares da un número impar. Podemos escribir
formalmente nuestra solución de la siguiente manera.
Si los cinco números son
A, B, C , D y E , podemos expresarlos como:
A = 2a + 1 , B = 2b + 1 , C = 2c + 1 , D = 2d + 1 , y E = 2e + 1
Entonces, su suma es:
S = A + B + C + D + E = ( 2a + 1) + ( 2b + 1) + ( 2c + 1) + ( 2d + 1) + ( 2e + 1)
⇒ S = 2a + 2b + 2c + 2d + 2e + 5 = 2 ( a + b + c + d + e + 2 ) + 1 , que es número impar.
Por lo tanto, su suma nunca será igual a 100.
EJEMPLO 5.
¿ Podrá un tablero 5x5, ser llenado mediante fichas de dominó?
Si es un tablero 5x5, entonces tendrá 25 casillas. Por otro lado, las fichas de domino cubren exactamente dos
casillas cada una y un número n de fichas cubrirán un número par de casillas (exactamente 2n ). Como 25 es
impar, se deduce que no se puede.
Olimpíadas Costarricenses de Matemática
7
OLCOMA
EJEMPLO 6.
Capítulo II: Lógica
a) Dado un polígono regular de 101 lados. Pruebe que si tuviese un eje de simetría, entonces
este pasa por exactamente un vértice y por el punto medio de un lado.
b) ¿Qué se puede decir de un decágono convexo regular?
a) Supongamos que tiene un eje de simetría. Como hay 101 = 2 ⋅ 50 + 1 vértices en la figura, entonces 50 están
en un semiplano y 50 están del otro. El vértice que sobra está en ninguno o en ambos de ahí que el eje de
simetría debe pasar por este punto.
Ahora, debe de existir un lado que tenga un vértice en un semiplano y otro vértice en el otro semiplano. Veamos
por qué. Si no existiera un lado con esa condición, entonces la figura sería cerrada en un semiplano lo que
implicaría que el eje de simetría pasaría por fuera de la figura, lo cual es absurdo. Analicemos el lado que tiene un
vértice en cada semiplano, el eje de simetría lo debe dividir en dos segmentos simétricos, de ahí que tienen la
misma longitud. Por lo tanto, el eje de simetría debe de pasar por el punto medio de algún lado.
b) Supongamos que existe un eje de simetría. Utilizaremos la estrategia de dividir en casos. Como el decágono
tiene 10 vértices hay dos posibilidades.
CASO No.1: El eje de simetría no pasa por ningún vértice, esto quiere decir que habrán 5 vértices y 4 lados
enteros en cada semiplano, de ahí que el eje de simetría intersecaría dos lados y por un análisis semejante al
anterior llegaríamos a que los biseca.
CASO No. 2: El eje de simetría pasa por dos vértices, esto quiere decir que hay cuatro vértices en cada semiplano
y cinco lados completos, de ahí que no interseca ningún lado.
Entonces en el caso, de un polígono regular con un número par de lados no se puede garantizar que un eje de
simetría pase por el punto medio de un lado
EJEMPLO 7.
Pedro compró un cuaderno con 96 hojas y las enumeró las páginas desde 1 hasta 192. Víctor
tomó el cuaderno de Pedro y arrancó 25 hojas (al azar o consecutivas) y luego sumó los 50
números que encontró en las hojas. ¿Pudo Víctor obtener 1990 como total?
Veamos que cualquier hoja que haya tomado tiene una página con un número par y otro impar, su suma es impar,
si sumamos 25 números impares obtendremos un resultado impar de ahí que nunca podrá ser igual a 1990.
EJEMPLO 8.
El producto de 22 números enteros es 1. ¿Podría su suma ser 0?
Primero es necesario ver que los números pueden ser únicamente 1 o –1. Ahora si el producto es 1 quiere decir
que los posibles números negativos se cancelan, lo que implica que hay un número par de ellos. Por otro lado, si
la suma es 0 es porque hay la misma cantidad de 1’s que de –1’s ⇒ hay 11 unos y 11 menos unos, un número
impar. Por lo tanto, es imposible.
Ejercicios:
1.
Todas las fichas de un juego de domino están en cadena (de tal forma que el número con que termina un domino concuerda
con el número con que empieza el domino adyacente). Si la cadena empieza con el número 5, ¿con qué número termina?
2.
Si usted tuviese un billete de ¢25, lo podría cambiar usando en total 10 monedas de ¢1,¢3 y ¢5?
3.
25 muchachos y 25 muchachas están sentados en un círculo. Muestre que existe algún estudiante que tenga sus dos vecinos
hombres.
4.
a) Suponga que tenemos 16 bombillos arreglados como en un tablero 4x4. Todos los bombillos están apagados y cada vez
que se toca un bombillo cambian de estado (prendido o apagado) todos los bombillos de la fila y de la columna del bombillo
tocado. Demuestre que existe una forma de tocar los bombillos en la cual todos los bombillos quedan encendidos.
b) Si hay 25 bombillos (arreglo 5 x 5) ¿Será posible? Si su respuesta es sí halle el mínimo número de toques.
8
Olimpíadas Costarricenses de Matemática
OLCOMA
Capítulo II: Lógica
EJEMPLO 9.
Si n es un entero positivo talque 2n+1 es un cuadrado perfecto. Pruebe que n+1 es la suma de
dos cuadrados perfectos consecutivos.
Literalmente el problema nos dice que
2n + 1 = k 2 donde k es entero, pero no solo eso, sino que k 2 es un entero
impar, de donde k también lo es. Una notación más efectiva sería decir que k = 2t + 1 donde
t es entero. Se
sigue que:
2n + 1 = k 2 = (2t + 1) 2 = 4t ² + 4t + 1 , de donde
n = 2t 2 + 2t ⇒ n + 1 = 2t 2 + 2t + 1 = t 2 +(t 2 + 2t + 1) = t 2 + (t + 1) 2
EJEMPLO 10.
Sean
a , b y c las longitudes de los lados de un triángulo.
Muestre que
3 ( ab + bc + ca ) ≤
(a + b + c)
2
≤ 4 ( ab + bc + ca )
En la mayor parte de las desigualdades nuestro primer intento es “cocinando” pues las desigualdades suelen ser
reformulaciones de hechos conocidos, mediante un camino que hay que descubrir.
En lado izquierdo de la desigualdad dice:
3 ( ab + bc + ca ) ≤
(a + b + c)
Multiplicando por 2,
0 ≤ 2a 2 + 2b 2 + 2c 2 − 2ab − 2bc − 2ac = (a − b) 2 +(b − c) 2 + (a − c) 2 lo cual es cierto pues
2
⇔ 3ab + 3bc + 3ca ≤ a 2 + b 2 + c 2 + 2ab + 2bc + 2ca ⇔ 0 ≤ a 2 + b 2 + c 2 − ab − bc − ca
el cuadrado de un número real siempre es no negativo y la suma de estos también lo es.
Para el otro lado de la desigualdad,
(a+b+c)² ≤ 4(ab+bc+ca) ⇔ a²+b²+c² + 2ab+2bc+2ac ≤ 4ab+4bc+4ca
⇔ a²+b²+c² ≤ 2ab + 2bc + 2ac = a(b+c) + b(a+c) + c(a+b).
Para establecer esta última desigualdad y por tanto concluir lo que queremos, basta deducir de la desigualdad
triangular que a²≤a(b+c),
b² ≤ b(a+c) y c² ≤ c(a+b) y sumar estas desigualdades.
AB un diámetro. Si BM es tangente a S; CF es
tangente al círculo en E e interseca BM en C. La cuerda AE al ser prolongada, interseca
BM en D. Pruebe que BC = BD .
EJEMPLO 11.
Sea S una circunferencia de centro O,
Suponga que BC=CD. Entonces CE=CD ya que CB=CE por que son ambas tangentes a S desde un mismo
punto. Tenemos que ∠CED = ∠CDE. Note que podemos deducir de esto que ∠CEB ≅ ∠BAE porque los ángulos
los triángulos ∆AEB y ∆ABD son rectángulos. Sin embargo, ∠CEB ≅ ∠BAE se podía deducir de que ambos
inscriben el mismo arco en S, así devolviéndose en las observaciones obtenemos la prueba.
Ejercicios:
1. Si 3n + 1
2.
3.
n + 1 es la suma de tres cuadrados perfectos.
2
n
n ( n − 1)
1
2
Demuestre que para todo número real x , ∑ k  x −  ≥
k  2 ( 2n + 1)

k =1
es un cuadrado perfecto, pruebe que
n > 1 equipos, jugaron exactamente una vez todos contra todos. Sea Gr y Pr el
número de partidos ganados y perdidos del r-ésimo equipo. Recordando que en el Basketball no hay empates, pruebe que
En un campeonato de Basketball, con
n
∑G
2
r
r =1
=
n
∑P
2
r
r =1
Olimpíadas Costarricenses de Matemática
9
OLCOMA
Capítulo II: Lógica
EJEMPLO 12.
Se escriben los números del 1 al 10 alrededor de un círculo en cualquier orden. Demostrar
que siempre es posible encontrar tres de ellos en posiciones consecutivas sobre el círculo
cuya suma sea al menos 17.
Supongamos que el enunciado es falso. Así “Cualesquiera tres números en posiciones consecutivas suman
menos o igual a 16”. Un buen ejercicio es que te preguntes por qué esta es la negación del enunciado.
Se sigue que:
A1 + A2 + A3 ≤ 16
A2 + A3 + A4 ≤ 16
:
A9 + A10 + A1 ≤ 16
Donde cada número aparece tres veces, sumando estas desigualdades
3(A1 + A2 +K+ A10 ) ≤ 10·16 ⇒ 3(1+2+K+10) ≤ 160 ⇒ 165 ≤ 160 lo que es absurdo, de donde el enunciado es
falso y probamos lo que queríamos.
EJEMPLO 13.
Dados a , b, c enteros impares, pruebe que la ecuación
racionales.
ax 2 + bx + c = 0 no tiene raíces
Supongamos lo contrario. Es decir, la ecuación ax + bx + c = 0 tiene una raíz racional. Sea
2
pérdida de generalidad podemos suponer que alguno
p o q es impar. ¿Por qué?
Bien, sustituyendo en la ecuación original y simplificando tenemos
CASO No. 1:
también, pero
CASO No.2:
p
esta raíz, sin
q
ap 2 + bpq + cq 2 = 0 . Dividiendo en casos:
p es par. Si p es par entonces ap 2 + bpq es par también, y por consiguiente cq 2 debe serlo
c y q son ambos impares, de donde hay contradicción.
q es par. Es un razonamiento análogo al caso No.1.
2
2
CASO No.3: p y q son ambos impares. Entonces, ap , bpq , cq son los tres impares, pero esto contradice
ap 2 + bpq + cq 2 = 0 pues la suma de tres impares es impar.
10
Olimpíadas Costarricenses de Matemática
OLCOMA
Capítulo II: Lógica
D. Principio del Palomar1
En el mundo de las matemáticas existen problemas, con un alto grado de dificultad, que suelen resolverse con los
teoremas o principios más “básicos” y “sencillos”, sí entre comillas, porque muchas veces conocemos la mayoría de
los teoremas y por más “sencillo” que sea el enunciado de estos se nos dificulta la aplicación de los mismos.
Lo que hace fascinante el resolver un problema cuyo enunciado aparenta un alto grado de dificultad es el poder
resolverlo en la forma más clara y sencilla posible; por ello estudiaremos uno de los principios, que a mi parecer, tiene
uno de los enunciados más sencillos y fáciles de entender, además de ser muy útil en el mundo de las matemáticas, y
muy particularmente en el mundo de las Olimpiadas de Matemática, este principio es el del Palomar, de los casilleros
o (como lo llaman los más doctos o más adentrados en el tema) el principio de Dirichlet.
Ahora supongo que desean que me deje de tantos rodeos y entre en detalle con respecto al principio del que les
he estado hablado; bueno antes de entrar de lleno con el enunciado del mismo veamos un ejemplo que les ayudara a
1
2
entenderlo mejor. Supongamos que 5 matletas se reúnen a celebrar el haber resuelto un problema bastante difícil. Y
deciden entonces ir a comer hamburguesas. Resulta que van al restaurante MathDonalds y piden la promoción del
momento: 6 hamburguesas, 1 coca de dos litros y una orden suprema de papas. Ahora resulta que tanto la coca como
las papas deciden compartirlas, pero existe un problema con las hamburguesas, que sobra una y debe repartirse entre
5 (algo muy rudo de hacer). Por ello el grupo decide que la hamburguesa no se partirá, sino que será rifada. Bueno, es
claro que uno de los 5 matletas resultara favorecido con 2 hamburguesas, pues esto que acaba de suceder no es mas
ni menos que lo que nos indica el principio del palomar.
Veamos en forma más general el enunciado del principio del palomar:
Si se tienen
N + 1 palomas en N palomares, entonces habrá un palomar que tendrá al menos dos palomas.
O en forma aun mucho más general:
Si se tienen
N ⋅k +1
palomas en
N palomares, entonces habrá un palomar que tendrá al menos k + 1
palomas.
Como muchos de ustedes se habrán percatado ya, el principio es en sí fácil de entender, pero como mencione
antes, lo difícil es el saber o poder aplicarlo a la solución de problemas propuestos, por ello para entender mejor como
aplicar este principio, resolveremos algunos problemas interesantes al respecto.
1
Elaborado por Wilson Tenorio.
Olimpíadas Costarricenses de Matemática
11
OLCOMA
EJEMPLO 14.
Capítulo II: Lógica
Una bolsa contiene canicas de cinco colores: rojas, azules, verdes, blancas y negras. ¿Cuál
es el numero más pequeño de canicas que podemos sacar de la bolsa, sin mirar, de modo que
tengamos la seguridad de que tenemos al menos dos canicas del mismo color? (wtenorio)
Probaremos que el numero más pequeño de canicas que podemos sacar con la seguridad de que al menos dos
son del mismo color es 6; primero veamos si sacamos solo cinco canicas entonces cabe la posibilidad que todas
sean de un color diferente lo cual no cumple con lo pedido en el problema; ahora como solo son cinco colores
(palomares) y si sacamos seis canicas (palomas) existen entonces al menos dos canicas (palomas) del mismo
color (palomares), esto por el principio del palomar, con lo cual queda probado el mínimo de canicas que debemos
sacar es 6.
Como tal vez pudo notar la dificultad en el uso de este principio es el diferenciar quienes son las palomas y
quienes los palomares, por ello estudiaremos otros ejercicios que nos ayudaran a diferenciar estos dos elementos.
EJEMPLO 15.
La ciudad de Leningrado tiene 5 millones de habitantes. Muestre que hay dos personas con la
misma cantidad de cabellos en su cabeza, si es conocido que una persona no puede tener
mas que un millón de cabellos en su cabeza. (Mathematical Circles)
Tenemos 1 000 001 palomares (numero cabellos posibles en la cabeza, tomando en cuenta a las personas sin
cabello) y además 5 000 000 palomas (número de personas) entonces podemos ver que existen más palomas
(personas) que palomares (numero de cabellos) por lo tanto hay un palomar con al menos dos palomas, en otras
palabras hay al menos dos personas con la misma cantidad de cabellos en su cabeza.
EJEMPLO 16.
Si se tienen 8 enteros. Muestre que se pueden escoger dos de ellos de tal forma que su
diferencia sea divisible por 7.
Antes de empezar con el problema en sí, vamos a ver unos resultados importantes que nos ayudaran con la
solución del mismo. A estos resultados les llamaremos “Lemas”.
Lema 1: Si dos números al ser divididos por X tienen el mismo residuo, entonces la diferencia entre estos dos
números es divisible por X.
Lema 2: Si un numero al ser dividido por X tiene residuo r entonces los posibles valores de r son 0, 1, 2, 3, 4, ...,
X-1.
Tal vez en este momento usted se pregunte que tienen que ver estos resultados con el problema en sí, pero
veamos lo siguiente:
Debido al lema 2 los posibles residuos de un numero al ser dividido por 7 son 0, 1, 2, 3, 4, 5, 6 es decir tenemos 7
residuos posibles, ahora si los posibles residuos representan a los palomares y los 8 enteros a las palomas
entonces se tiene, por el principio del palomar, que al menos dos enteros tienen el mismo residuo al ser divididos
por 7. Ahora debido al lema 1 como existen dos enteros que tienen el mismo residuo al ser divididos por 7
entonces su diferencia es divisibles por 7, con lo cual se ha probado lo pedido en el problema.
12
Olimpíadas Costarricenses de Matemática
OLCOMA
EJEMPLO 17.
Capítulo II: Lógica
Veinticinco cajas de manzana son enviadas a un almacén. Las manzanas son de tres tipos
diferentes, y todas las manzanas en cada caja son del mismo tipo. Probar que hay al menos
nueve cajas que contienen el mismo tipo de manzanas. (Mathematical Circles)
Veamos que en este caso los tipos de manzana representan a los palomares y la cantidad de cajas a las palomas,
entonces como
25 = 3 ⋅ 8 + 1 , se tiene que por en principio del palomar (en su forma general), existen al menos
8 + 1 = 9 cajas con manzanas del mismo tipo.
Otra forma de abarcar el problema es la siguiente: supongamos que existen a lo sumo 8 cajas de manzanas de
cada tipo es decir tendríamos en total 24 cajas pero como son 25 cajas, la que falta, por el principio del palomar,
debe ser de alguno de los tres tipos de manzanas por lo tanto se tendría que uno de los tipos de manzana están
depositados en al menos 9 cajas.
EJEMPLO 18.
Probar que en un grupo de cinco personas, al menos dos personas tienen un número idéntico
de amigos en el grupo. (Mathematical Circles)
Para la solución de este problema podemos tomar en cuenta dos casos:
Caso 1: Supongamos que cada persona (palomas) tiene al menos un amigo en el grupo, entonces una persona a
lo sumo puede tener cuatro amigos, por lo tanto existen cuatro palomares (solo un amigo, dos amigos, tres
amigos o cuatro amigos) por lo tanto, por el principio del palomar, existe al menos dos personas con la misma
cantidad de amigos en el grupo.
Caso 2: Supongamos existe al menos una persona que no tiene amigos en el grupo, entonces una persona a lo
sumo puede tener tres amigos, por lo tanto existen cuatro palomares (ningún amigo, un amigo, dos amigos o tres
amigos) por lo tanto, por el principio del palomar, existe al menos dos personas con la misma cantidad de amigos
en el grupo.
EJEMPLO 19.
Suponga que cada cuadrado de un tablero de 3 por 7, es coloreado de blanco o negro. Probar
que sin importar como sea coloreado, el tablero contiene un rectángulo (formado por las
líneas horizontales y verticales del tablero), como la zona punteada en la figura 1, tales que
todas las esquinas del rectángulo son del mismo color.
Figura 1
Como existen siete rectángulos en un tablero de 3 por 7. La configuración de las columnas es de alguno de los
tipos que tenemos en la figura 2.
Figura 2
Olimpíadas Costarricenses de Matemática
13
OLCOMA
Capítulo II: Lógica
Supongamos que una de las columnas es del tipo 1. Nosotros tendríamos resuelto el problema si alguna de las
otras 6 columnas es del tipo 1, 2, 3 o 4. Pero supongamos que cada una de las otras es del tipo 5, 6, 7 o 8.
Entonces por el principio del palomar, dos de estas siete columnas son del mismo tipo, con lo cual ya estaría
resuelto el problema.
En forma análoga se prueba si una de las columnas es del tipo 8.
Ahora supongamos que ninguna de las columnas es del tipo 1 o tipo 8. Entonces nosotros tenemos siete
columnas pero solo seis tipos. Por el principio del palomar, dos columnas son del mismo tipo, con lo cual la
prueba estaría completa.
EJEMPLO 20.
Si entre 15 muchachos trajeron cien naranjas. Pruebe que un par de ellos trajeron la misma
cantidad de naranjas.
Veamos que si todos los muchachos traen una cantidad diferente de naranjas, es decir, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14 y 15 naranjas, entonces la suma seria 120 naranjas, pero como serian mas naranjas que las traídas
por los muchachos, por el principio del palomar, alguna de estas cantidades se debe de repetir.
EJEMPLO 21.
Si se toman siete números enteros positivos menores que 13, probar que siempre es posible
tomar dos de ellos cuya suma es 13.
Veamos que los números con los que podemos trabajar este problema serian 1, 2, 3, 4, 5, K , 11, 12; ya que son
los únicos que cumplen con la condición de ser menor que 13; con estos números se pueden formar la siguientes
parejas:
1,12 , 2,11 , 3,10 , 4,9 , 5,8 , 6, 7 en las cuales podemos notar que cada par de números encerrados
en un cuadrito posee suma igual a 13, ahora si solo tomamos uno de los números de cada pareja (palomares)
tendríamos seis números de los cuales ningún par de estos suma 13, pero como se nos pide tomar siete números
(palomas), por lo tanto, por el principio del palomar, en alguno de los cuadritos van a estar los dos números, los
cuales, debido al acomodo que se hizo, suman 13.
EJEMPLO 22.
Muestre que si se tienen cinco números (no necesariamente diferentes), uno siempre puede
escoger tres de ellos cuya suma sea divisible por 3.
Primero recordemos que si a un número lo dividimos por 3 los posibles residuos que podemos obtener serian 0, 1
ó 2 (Lema 2 del problema 3) Ahora para resolver este problema supongamos dos casos:
Caso I: Veamos que si al menos tres de los cinco números tomados tienen el mismo residuo al ser divididos por
tres entonces las posibles sumas (al escoger tres números con igual residuo) de los tres residuos serian 0, 3 ó 6
por lo tanto como 0, 3 y 6 son divisibles por 3 la suma de los números también lo serian.
Caso II: Ahora si a lo sumo tenemos dos residuos iguales dentro de los cinco números, por el principio del
palomar al menos existe un numero con residuo 0, otro con residuo 1 y otro con residuo 2, entonces al sumar
éstos la suma de sus residuos nos resulta 3 (que por supuesto es divisible por 3) , es decir, la suma de las tres
numero también será divisible por 3. En este problema debemos notar que los cinco números representan a las
palomas y las parejas de residuos representan a los palomares.
14
Olimpíadas Costarricenses de Matemática
OLCOMA
EJEMPLO 23.
Capítulo II: Lógica
Si se tiene un conjunto con diez números naturales, probar que siempre es posible encontrar
que alguno o la suma de algunos de ellos es divisible por 10.
Supongamos que los números que nosotros tenemos son: ♣, ♦, ♥, ♠, ∆, &, Φ, Χ, ⊗,  y , ahora si alguno de
estos números es divisible por 10 ya estaría resulto el problema; supongamos entonces que ninguno de estos
números es divisible por 10, y que se tienen las siguientes sumas:
veamos que si alguna de estas sumas es divisible por diez ya estaría resulto el problema, por lo cual también
supondremos que ninguna de estas sumas es divisible por diez, es decir deben dejar algún residuo al ser
divididas por 10, entonces recurriendo al lema 2 del problema 3, tenemos que los posibles residuos (palomares)
serian 1, 2, 3, 4, 5, 6, 7, 8, 9 (el cero no se toma en cuenta pues si alguna suma deja residuo cero al ser dividido
por diez ésta seria divisible por diez, lo cual contradice nuestra suposición), ahora como se tienen diez sumas S1,
S2, S3, S4, S5, S6, S7, S8 ,S9, S10 (palomas) y nueve posibles residuos (palomares), por el principio del
palomar, existen dos sumas con igual residuo, es decir, que si restamos estas dos sumas cuyo residuo es el
mismo, el resultado seria divisible por 10 (Lema 2, problema 3), con lo cual estaría resuelto el problema.
Nota: Supongamos, por ejemplo, que las sumas cuyo residuo es el mismo son S3 y S8, entonces su resta seria:
, en la cual podemos ver que también es una suma de los números que
tenemos.
EJEMPLO 24.
Dado cualquier subconjunto A de diez enteros del conjunto
, demuestre que
siempre habrá dos subconjuntos disjuntos de A cuyos elementos tienen la misma suma.
Para empezar recordemos que si se tiene un conjunto con diez elementos se pueden formar
subconjuntos no vacios. Y cada subconjunto se puede asociar con la suma de sus elementos, entonces nótese
que la mayor suma posible seria:
. Por lo tanto existen dos subconjuntos
no necesariamente disjuntos tales que la suma de sus elementos es la misma. Ahora hay dos posibilidades:
Si los dos subconjuntos con igual suma son disjuntos pues ya estaría demostrado lo que se nos pide.
Si los dos subconjuntos con igual suma no son disjuntos entonces basta con restar los elementos que se tienen
en común estos dos subconjuntos, lo cual generaría dos nuevos subconjuntos pertenecientes al conjunto A con
igual suma y además disjuntos.
Por lo tanto en cualquiera de los casos es posible encontrar dos conjuntos con las características enunciadas.
Olimpíadas Costarricenses de Matemática
15
OLCOMA
Capítulo II: Lógica
EJEMPLO 25.
Muestre que existe un numero de la forma 199...91 (con más de dos nueves) que es múltiplo
de 1991.
Para iniciar notemos que como existen infinitos números de la forma 199K91 y únicamente 1991 posibles
residuos al dividir un número por 1991, entonces si alguno de los números tuviese residuo cero pues ya estaría
resuelto el problema. Ahora supongamos que tenemos un conjunto infinito de números de la forma sugerida pero
en el cual ninguno de los números posee residuo cero al ser dividido por 1991 entonces por el principio del
palomar existen al menos dos números cuyo residuo al ser divididos por 1991 es el mismo, supongamos que
estos números son los siguientes:
y
donde m>n. Entonces si restamos estos dos números
se obtiene el siguiente número:
el cual es evidentemente divisible por 1991, esto gracias a los lemas que estudiamos en los problemas anteriores.
Ahora si a este número le quitamos la fila de ceros que posee al final entonces el resultado seguiría siendo
divisible por 1991, por lo tanto vamos a eliminar los ceros del final excepto a tres de ellos con lo cual el número
que se formaría sería el siguiente:
Este número es aun divisible por 1991 y por lo tanto si le sumamos a este el número 1991 aun seria divisible por
1991 y se formaría el siguiente numero:
Por lo tanto este número es de la forma pedida y también es divisible por 1991. Se puede afirmar además que
existen infinitos números de esta forma con la propiedad dada.
Problemas Propuestos: En esta sección se presentan algunos problemas cuyo solución se basa en el principio del
palomar, por ello se deja al lector la solución de los mismo.
1.
Demuestre que si 8 personas están en una habitación, al menos dos de ellas cumplen años el mismo día de la semana.
2.
¿Cuántas veces debemos tirar un sólo dado para obtener el mismo resultado
al menos dos veces? R/7
3.
al menos tres veces?
R/13 al menos n veces, para
n ≥4?
R/
6 ( n − 1) + 1
Se lanzan tres dados al mismo tiempo en 17 ocasiones, y en cada ocasión se suman los valores de la cara superior de cada
dado. Muestre que siempre se repite al menos un par de veces algún resultado al finalizar los 17 lanzamientos.
4.
Sea un cuadrado de diagonal 3 en el que marcamos 10 puntos al azar. Demostrar que siempre tenemos al menos dos puntos
que están a distancia no mayor que 1.
5.
Muestre que si se tienen 5 números potencias de 3, siempre es posible tomar dos de ellos de forma que su diferencia sea un
divisible por 10.
6.
En un campamento con 13 personas se sabe que la suma de sus edades es 555 años, pruebe que se pueden escoger 5 de las
personas, de modo que la suma de sus edades sea mayor que 210.
7.
Demostrar que dados
o igual que
8.
16
n
números naturales
x 1 , x 2 , x 3 ,..., x n
tales que su suma vale
S
, alguno de ellos ha de ser mayor
S n.
Un conjunto
X
de 100 elementos se parte en 14 Bloques. Probar que hay dos bloques con el mismo número de elementos.
Olimpíadas Costarricenses de Matemática
OLCOMA
9.
Capítulo II: Lógica
Diez estudiantes resuelven en total 35 problemas en una olimpiada de matemática. Cada problema es resuelto por
exactamente un estudiante. Se sabe que al menos un estudiante resolvió exactamente un problema, al menos un estudiante
resolvió exactamente dos problemas y al menos un estudiante resolvió tres problemas. Probar que al menos un estudiante
resolvió al menos cinco problemas.
10. De los siguientes 34 números, 1, 4, 7, 10, 13, K, 97, 100. Demuestre que si se eligen 19 de estos, siempre hay dos cuya suma
es 104. (Putnam 1978)
11. Cincuenta y un puntos se distribuyen sobre un cuadrado de 1x1. Demuestre que hay al menos 3 puntos que pueden ser
cubiertos por un cuadrado de
.
12. Se tiene un conjunto formado por diez números distintos de dos cifras, pruebe que es posible seleccionar dos subconjuntos
cuyos elementos tienen igual suma.
13. Demuéstrese que entre siete enteros positivos distintos menores o iguales que 126, siempre se puede conseguir dos de ellos a
.
y b que satisfacen que:
14. Hay 100 personas sentadas en una mesa circular, y al menos 51 de ellas son hombres. Probar que hay dos hombres sentados
en posiciones diametralmente opuestas de la mesa.
15. Las 9 casillas de una cuadricula de 3x3 son llenadas aleatoriamente por los números
−1 , 0
y
1.
Probar que entre las 8
sumas que se obtienen por filas, columnas y diagonales hay dos iguales.
16. Se dispone de 100 tarjetas, numeradas del 100 al 999. El valor de cada tarjeta es la suma de los dígitos que aparecen en ella
(los posibles valores de estas sumas van de 1 a 27). ¿Cuál es el número mínimo de tarjetas que hay que extraer para asegurar
que haya tres con el mismo valor? R/53
17. Pruebe que entre
enteros, siempre habrá dos cuya diferencia será divisible por
.
18. La universidad X tiene 13 777 estudiantes y el Rector de dicha institución le pide a estos que cada uno escriba un numero par
de cinco dígitos distintos en un papel (sin decir el numero que escribió) y lo depositen en una caja. Pruebe que después de
revisar todos los papeles depositados el Rector encuentra al menos dos con el mismo número. ¿Pasará lo mismo si fuesen 13
776 estudiantes? (wtenorio)
19. Se dan 25 puntos en el plano. Se sabe que dados cualesquiera tres de ellos, hay dos a distancia menor o igual que 1. Probar
que hay 13 que están dentro de un círculo de radio 1.
20. Demuestre que se pueden tomar 55 números cualesquiera menores o iguales que 100 tales que siempre hay dos de ellos
cuya diferencia es 10.
21. Márquese a un disco con la etiqueta “1”, a dos discos con la etiqueta “2”, a tres discos con la etiqueta “3”, . . . , a cincuenta
discos con la etiqueta ‘‘50”. Póngase a estos 1+2+3+———+50 = 1275 discos en una caja. Se sacan luego discos de la caja, al
azar y sin remplazo. ¿Cuál es el número mínimo de discos que se debe sacar para garantizar al menos diez discos con la
R/415
misma etiqueta? (AHSME 1994)
22. Dados cualesquiera 9 enteros cuyos factores primos están en el conjunto {3, 7, 11}, demuéstrese que habrá dos cuyo producto
es un cuadrado perfecto.
23. Si se toman
enteros del conjunto
, demuéstrese que siempre hay dos tales que:
Son primos relativos.
El menor dividirá (sin dejar residuo) al mayor.
24. Sea
un número natural. Probar que, dados
bien su diferencia es divisible por
números enteros cualesquiera, siempre hay dos tales que bien su suma,
. (Olimpiada Británica, 1966)
25. Sea un cuadrado de diagonal 3 en el que marcamos al azar 10 puntos. Demostrar que siempre tenemos al menos dos puntos
que están a distancia no mayor que 1.
Olimpíadas Costarricenses de Matemática
17
OLCOMA
18
Capítulo II: Lógica
Olimpíadas Costarricenses de Matemática