Principio de las casillas

No es lo primero pero si es el principio en combinatoria:

Dice asi:
Si metemos n+1 fichas en n casillas siempre queda al menos una casilla con 2 fichas

Y tiene una generalización:
Si ponemos kn+1 fichas en n casillas, siempre quedan al menos k+1 fichas en una misma casilla
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 n números cuya suma no es divisible por n hay al menos uno mayor que el promedio

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 n veces el promedio, que es la suma total, contradicción!

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 2\pi

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

7 comentarios en “Principio de las casillas

  1. 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.

  2. 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)

  3. Si coloreamos las aristas de una gráfica completa de 6 vértices, entonces hay dos triángulos monocromático (no necesariamente ambos triángulos del mismo color).

    Intentenlo, está chevere el problemita (dejaré la demostración para el 6 de enero)

  4. Pingback: De nuevo el principio de Dirichlet | ¿Quieres problemas?

incluye tu respuesta

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s