Principio de las casillas Noviembre 25, 2007
Posted by Álvaro in combinatoria, teoremas.Tags: principio de casillas, promedio
trackback
No es lo primero pero si es el principio en combinatoria:
Dice asi:
Si metemos 
Y tiene una generalización:
Si ponemos 
es muy fácil de escribir su demostración, por eso sugiero que la intenten antes de seguir leyendo:
Puesto en otras palabras (a veces es mas útil de esta forma)
en un conjunto de
De hecho la demostración es mas fácil puesto así, por reducción al absurdo: si todos los números fueran menores que el promedio, su suma sería menor que
No siempre se aplica a cantidades enteras, también a números reales, por ejemplo el siguiente teorema es una aplicación directa del principio de las casillas:
En un hexágono convexo hay 3 vértices cuyos ángulos internos suman mas de
Y por supuesto uno de los teoremas mas bellos y famosos de combinatoria es también consecuencia directa del principio de casillas
En un grupo de 6 personas hay siempre 3 que se conocen entre sí o 3 que no se conocen en absoluto
Álvaro
faryshta
ssbmplayer
matetam
lxtreme
El siguiente es un buen ejercicio del principio de casillas:
Hay dibujados 25 puntos en el plano de forma que de cada 3 de ellos, 2 distan menos de 1 cm entre ellos.
Demostrar que hay un circulo de radio 1 que contiene a al menos 13 de ellos.
El teorema de las 6 personas se le conoce como Teorema de Ramsey, y se enuncia en terminos de una coloración de gráficas:
Si coloreamos las aristas de una gráfica completa de 6 vértices, entonces hay un triángulo monocromático, es decir, un triángulo formado por 3 aristas del mismo color.
La demostración es bastante sencilla:
En cada vértice hay 5 aristas de 2 colores (Azul y Blanco), tomemos alguno, por el principio de casillas debe haber 3 aristas del mismo color, digamos Azul. Los otros extremos de esas aristas son 3… si entre ellos hay una arista azul entonces hay un triángulo Azul con 2 de las aristas que salen del primer vértice. … Si todas las aristas entre esos 3 vértices son Blancas, entonces se forma un triángulo blanco :)
(en ambos casos hay un triángulo de un solo color)
aquí está una explicación con dibujos (en inglés)
Un problema relacionado:
Por acá.
Saludos a todos.