PRINCIPIO DE PIGEONHOLE

El PIGEONHOLE , también conocido como Dirichlet 's caja (o cajón) principio, se establece que, habida cuenta de dos números naturales m y n con n> m, n elementos si se ponen en m casilleros, entonces por lo menos un casillero debe contener más de Un elemento. Another way of stating this would be that m holes can hold at most m objects with one object to a hole; adding another object will force one to reuse one of the holes, provided that m is finite. Otra manera de indicar que este sería m agujeros pueden tener m en la mayoría de los objetos con un objeto a un agujero; añadir otro objeto fuerza uno a la reutilización uno de los agujeros, a condición de que m es finita. More formally, the theorem states that there does not exist an injective function on finite sets whose codomain is smaller than its domain .

The pigeonhole principle is an example of a counting argument which can be applied to many formal problems, including ones involving infinite sets that cannot be put into one-to-one correspondence. El casillero principio es un ejemplo de un conteo argumento que se puede aplicar a muchos problemas formales, incluyendo la participación de los conjuntos infinitos que no se pueden poner en uno-a-uno correspondencia. In Diophantine approximation the quantitative application of the principle to the existence of integer solutions of a system of linear equations goes under the name of Siegel 's lemma . En Diophantine aproximación cuantitativa de la aplicación del principio de la existencia de soluciones entero de un sistema de ecuaciones lineales bajo el nombre de Siegel 's lema.

The first statement of the principle is believed to have been made by Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle" or "shelf principle"). La primera declaración del principio se cree que ha sido formulada por Dirichlet en 1834 con el nombre Schubfachprinzip ( "cajón de principio" o "plataforma principio"). In Italian too, the original name "principio dei cassetti" is still in use; in some other languages (for example, Russian) this principle is called the Dirichlet principle (not to be confused with the minimum principle for harmonic functions of the same name).

En italiano también, el nombre original "principio dei cassetti" todavía está en uso en algunos otros idiomas (por ejemplo, Rusia) este principio se le llama el principio de Dirichlet (no confundir con el mínimo principio de las funciones armónicas del mismo nombre).

La inspiración para el nombre del principio: palomas en agujeros. Here n = 7 and m = 9 so we can conclude that there are at least two empty pigeonholes. Aquí n = 7 m = 9 y por lo que podemos concluir que hay al menos dos casilleros vacíos. (There would be three if exactly two birds shared one hole.) (Habría tres si exactamente dos pájaros comparten un agujero

Ejemplos:

Hay varias personas en la sala. Some are acquaintances, others are not. Algunos son conocidos, otros no lo son. (Being acquainted is a symmetric non- reflexive relationship.) Show that some two people have the same number of acquaintances. (Estar familiarizado simétrico es una relación no reflexiva.) Mostrar que dos personas tienen el mismo número de conocidos.

Hint Sugerencia

If there are N people in the room and each has a different number of acquaintances then one is bound to have N-1 and one 0 acquaintances. Si hay N personas en la sala y cada uno tiene un número diferente de los conocidos entonces uno está obligado a tener N-1 y un 0 conocidos. This is a contradiction. Esto es una contradicción.

2) Consider a chess board with two of the diagonally opposite cremoved.Supongamos un tablero de ajedrez con dos de las esquinas opuestas   diagonalmente eliminado. Is it possible to cover the board with pieces of domino whose size is exactly two board squares? ¿Existe la posibilidad de cubrir el tablero con piezas de dominó, cuyo tamaño es exactamente dos plazas bordo?

Solution Solución

No, it's not possible. No, no es posible. Two diagonally opposite squares on a chess board are of the same color. Dos plazas diagonalmente opuesto en un tablero de ajedrez son del mismo color. Therefore, when these are removed, the number of squares of one color exceeds by 2 the number of squares of another color. Por lo tanto, cuando estos se eliminan, el número de plazas de un color supera por 2 el número de plazas de otro color. However, every piece of domino covers exactly two squares and these are of different colors. Sin embargo, cada pieza de dominó cubre exactamente dos plazas y son de diferentes colores. Every placement of domino pieces establishes a 1-1 correspondence between the set of white squares and the set of black squares. Cada colocación de las piezas de dominó 1-1 establece una correspondencia entre el conjunto de cuadrados blancos y el conjunto de negro plazas. If the two sets have different number of elements, then, by the Pigeonhole Principle, no 1-1 correspondence between the two sets is possible. Si los dos conjuntos tienen diferente número de elementos, entonces, por el principio Pigeonhole, 1-1 no correspondencia entre los dos conjuntos es posible.