En matemáticas , el principio del casillero establece que si se colocan n artículos en m contenedores, con n > m , entonces al menos un contenedor debe contener más de un artículo. [1] Por ejemplo, de tres guantes (ninguno de los cuales es ambidiestro/reversible), al menos dos deben ser para diestros o al menos dos para zurdos, porque hay tres objetos pero sólo dos categorías de zurdidad para poner ellos en. Esta afirmación aparentemente obvia, un tipo de argumento de conteo , puede usarse para demostrar resultados posiblemente inesperados. Por ejemplo, dado que la población de Londres es mayor que el número máximo de cabellos que puede tener una cabeza humana, el principio requiere que debe haber al menos dos personas en Londres que tengan el mismo número de cabellos en la cabeza.
Aunque el principio del casillero aparece ya en 1624 en un libro atribuido a Jean Leurechon , [2] comúnmente se le llama principio de caja de Dirichlet o principio del cajón de Dirichlet después de un tratamiento del principio en 1834 por Peter Gustav Lejeune Dirichlet bajo el nombre Schubfachprinzip ("cajón principio" o "principio de estantería"). [3]
El principio tiene varias generalizaciones y puede enunciarse de varias maneras. En una versión más cuantificada: para los números naturales k y m , si n = km + 1 objetos se distribuyen entre m conjuntos, el principio del casillero afirma que al menos uno de los conjuntos contendrá al menos k + 1 objetos. [4] Para n y m arbitrarios , esto se generaliza a , donde y denotan las funciones de piso y techo , respectivamente.
Aunque la aplicación más sencilla del principio es a conjuntos finitos (como palomas y cajas), también se utiliza con conjuntos infinitos que no pueden ponerse en correspondencia uno a uno . Para hacerlo se requiere la declaración formal del principio de casillero: "no existe una función inyectiva cuyo codominio sea menor que su dominio ". Las demostraciones matemáticas avanzadas como el lema de Siegel se basan en este concepto más general.
Dirichlet publicó sus obras tanto en francés como en alemán, utilizando el Schubfach alemán o el tiroir francés . El estricto significado original de estos términos corresponde al cajón inglés , es decir, una caja con la parte superior abierta que se puede deslizar dentro y fuera del mueble que la contiene . (Dirichlet escribió sobre la distribución de perlas entre los cajones). Estos términos se transformaron en casillero en el sentido de un pequeño espacio abierto en un escritorio, gabinete o pared para guardar cartas o papeles , arraigado metafóricamente en estructuras que albergan palomas.
Debido a que los muebles con casilleros se usan comúnmente para almacenar o clasificar cosas en muchas categorías (como cartas en una oficina de correos o llaves de habitaciones en un hotel), la traducción del casillero puede ser una mejor interpretación del "cajón" original de Dirichlet. Esa comprensión del término casillero , que se refiere a algunas características de los muebles, se está desvaneciendo (especialmente entre aquellos que no hablan inglés de forma nativa sino como lengua franca en el mundo científico) a favor de una interpretación más pictórica, que literalmente involucra palomas y agujeros. La sugerente (aunque no engañosa) interpretación de "casillero" como " palomar " ha encontrado últimamente su camino de regreso a una retrotraducción alemana del "principio del casillero" como " Taubenschlagprinzip ". [5]
Además de los términos originales " Schubfachprinzip " en alemán [6] y " Principe des tiroirs " en francés, [7] todavía se utilizan otras traducciones literales en árabe ( "مبدأ برج الحمام" ), búlgaro (" принцип на чекмеджетата "), Chino ("抽屉原理"), danés (" Skuffeprincippet "), holandés (" ladenprincipe "), húngaro (" skatulyaelv "), italiano (" principio dei cassetti "), japonés ("引き出し論法"), persa (" اصل لانه کبوتری "), polaco (" zasada szufladkowa "), portugués (" Princípio das Gavetas "), sueco (" Lådprincipen "), turco (" çekmece ilkesi ") y vietnamita (" nguyên lý hộp ").
Supongamos que un cajón contiene una mezcla de calcetines negros y calcetines azules, cada uno de los cuales se puede usar en cualquier pie. Sacas varios calcetines del cajón sin mirar. ¿Cuál es la cantidad mínima de calcetines quitados que se requieren para garantizar un par del mismo color? Según el principio del casillero ( m = 2 calcetines, usando un casillero por color), la respuesta es tres ( n = 3 artículos). O tienes tres de un color, o tienes dos de un color y uno de otro.
Si n personas pueden darse la mano entre sí (donde n > 1 ), el principio de encasillamiento muestra que siempre hay un par de personas que le darán la mano al mismo número de personas. En esta aplicación del principio, el "hueco" al que se asigna una persona es el número de manos que esa persona estrecha. Dado que cada persona le da la mano a un número determinado de personas de 0 a n − 1 , hay n huecos posibles. Por otro lado, el agujero "0", el agujero " n − 1" o ambos deben estar vacíos, ya que es imposible (si n > 1 ) que una persona estreche la mano de todos los demás mientras otra persona se da la mano. con nadie. Esto deja que n personas sean colocadas en como máximo n − 1 huecos no vacíos, por lo que se aplica el principio.
Este ejemplo de apretón de manos equivale a la afirmación de que en cualquier gráfico con más de un vértice , hay al menos un par de vértices que comparten el mismo grado . [8] Esto se puede ver asociando cada persona con un vértice y cada arista con un apretón de manos.
Se puede demostrar que debe haber al menos dos personas en Londres con la misma cantidad de pelos en la cabeza de la siguiente manera. [9] [10] Dado que una cabeza humana típica tiene un promedio de alrededor de 150.000 cabellos, es razonable suponer (como límite superior) que nadie tiene más de 1.000.000 de cabellos en la cabeza ( m = 1 millón de agujeros). Hay más de 1.000.000 de personas en Londres ( n es mayor que 1 millón de artículos). Al asignar un casillero a cada número de pelos en la cabeza de una persona, y asignar personas a casilleros de acuerdo con el número de pelos en sus cabezas, debe haber al menos dos personas asignadas al mismo casillero en la asignación número 1.000.001 (porque tienen el mismo número de pelos en la cabeza; o, n > m ). Suponiendo que Londres tiene 9,002 millones de habitantes, [11] se deduce que al menos diez londinenses tienen el mismo número de pelos, ya que tener nueve londinenses en cada uno de los 1 millón de casilleros representa sólo 9 millones de personas.
Para el caso promedio ( m = 150.000 ) con la restricción: menor número de superposiciones, habrá como máximo una persona asignada a cada casillero y la persona 150.001 asignada al mismo casillero que otra persona. En ausencia de esta restricción, puede haber casilleros vacíos porque la "colisión" ocurre antes de que llegue la persona número 150.001. El principio simplemente prueba la existencia de una superposición; no dice nada sobre el número de superposiciones (que cae bajo el tema de distribución de probabilidad ).
Hay una alusión pasajera y satírica en inglés a esta versión del principio en A History of the Athenian Society , antepuesta a A Suplement to the Athenian Oracle: Being a Collection of the Remaining Question and Answers in the Old Athenian Mercuries (impreso para Andrew Bell, Londres, 1710). [12] Parece que la pregunta es si había dos personas en el mundo que tuvieran el mismo número de cabellos en la cabeza. había sido planteado en The Athenian Mercury antes de 1704. [13] [14]
Quizás la primera referencia escrita al principio del casillero aparece en una breve frase de la obra Selectæ Propositiones del jesuita francés Jean Leurechon de 1622 : [2] "Es necesario que dos hombres tengan el mismo número de pelos, écus u otras cosas, como el uno al otro." [15] El principio completo se explicó dos años más tarde, con ejemplos adicionales, en otro libro que a menudo se ha atribuido a Leurechon, pero que podría ser de uno de sus alumnos. [2]
El problema del cumpleaños pregunta, para un conjunto de n personas elegidas al azar, ¿cuál es la probabilidad de que un par de ellas tengan el mismo cumpleaños? El problema en sí tiene que ver principalmente con probabilidades contraintuitivas, pero también podemos decir por el principio del casillero que si hay 367 personas en la habitación, hay al menos un par de personas que comparten el mismo cumpleaños con 100% de probabilidad, como hay sólo 366 cumpleaños posibles para elegir (incluido el 29 de febrero, si está presente).
Imaginemos siete personas que quieren jugar en un torneo de equipos ( n = 7 elementos), con una limitación de sólo cuatro equipos ( m = 4 hoyos) para elegir. El principio del casillero nos dice que no todos pueden jugar para equipos diferentes; debe haber al menos un equipo con al menos dos de los siete jugadores:
Cualquier subconjunto de tamaño seis del conjunto S = {1,2,3,...,9} debe contener dos elementos cuya suma sea 10. Los casilleros estarán etiquetados por los dos subconjuntos de elementos {1,9}, {2 ,8}, {3,7}, {4,6} y el singleton {5}, cinco casilleros en total. Cuando las seis "palomas" (elementos del subconjunto tamaño seis) se coloquen en estos casilleros, entrando cada paloma en el casillero que lo tiene contenido en su etiqueta, al menos uno de los casilleros etiquetados con un subconjunto de dos elementos tendrá dos palomas en él. [dieciséis]
El principio se puede utilizar para demostrar que cualquier algoritmo de compresión sin pérdidas , siempre que reduzca algunas entradas (como sugiere la "compresión"), también hará que otras entradas sean más grandes. De lo contrario, el conjunto de todas las secuencias de entrada hasta una longitud determinada L podría mapearse al conjunto (mucho) más pequeño de todas las secuencias de longitud menor que L sin colisiones (porque la compresión no tiene pérdidas), una posibilidad que el principio del casillero excluye.
Un problema notable en el análisis matemático es, para un número irracional fijo a , demostrar que el conjunto de partes fraccionarias es denso en [0, 1] . Se descubre que no es fácil encontrar explícitamente números enteros n, m tales que donde e > 0 sea un número positivo pequeño y a sea algún número irracional arbitrario. Pero si se toma M tal que , según el principio de encasillamiento, debe haber tal que n 1 a y n 2 a estén en la misma subdivisión entera de tamaño (solo hay M de tales subdivisiones entre números enteros consecutivos). En particular, se puede encontrar n 1 , n 2 tal que
para algunos p, q enteros y k en {0, 1, ..., M − 1 }. Entonces se puede comprobar fácilmente que
Esto implica que donde n = n 2 − n 1 o n = n 1 − n 2 . Esto muestra que 0 es un punto límite de {[ na ]}. Entonces se puede usar este hecho para probar el caso de p en (0, 1] : encontrar n tal que entonces si la prueba está completa. De lo contrario
y estableciendo
Se obtiene
Se presentan variantes en varias pruebas. En la prueba del lema de bombeo para lenguajes regulares , se utiliza una versión que mezcla conjuntos finitos e infinitos: si se colocan infinitos objetos en un número finito de cajas, entonces dos objetos comparten una caja. [18] En la solución de Fisk al problema de la galería de arte se utiliza una especie de proceso inverso: si se colocan n objetos en k cajas, entonces hay una caja que contiene como máximo objetos. [19]
Las siguientes son formulaciones alternativas del principio del casillero.
Sean q 1 , q 2 , ..., q n números enteros positivos. Si
los objetos se distribuyen en n cajas, entonces la primera caja contiene al menos q 1 objetos, o la segunda caja contiene al menos q 2 objetos, ..., o la enésima caja contiene al menos q n objetos. [21]
La forma simple se obtiene a partir de esto tomando q 1 = q 2 = ... = q n = 2 , lo que da n + 1 objetos. Tomando q 1 = q 2 = ... = q n = r se obtiene la versión más cuantificada del principio, a saber:
Sean n y r números enteros positivos. Si n ( r - 1) + 1 objetos se distribuyen en n cajas, entonces al menos una de las cajas contiene r o más objetos. [22]
Esto también se puede expresar como, si se van a asignar k objetos discretos a n contenedores, entonces al menos un contenedor debe contener al menos objetos, donde está la función techo , que denota el entero más pequeño mayor o igual a x . De manera similar, al menos un contenedor no debe contener más que objetos, donde está la función piso , que denota el número entero más grande menor o igual a x .
Una generalización probabilística del principio del casillero establece que si n palomas se colocan aleatoriamente en m casilleros con probabilidad uniforme 1/ m , entonces al menos un casillero contendrá más de una paloma con probabilidad
donde ( m ) n es el factorial descendente m ( m − 1)( m − 2)...( m − n + 1) . Para n = 0 y para n = 1 (y m > 0 ), esa probabilidad es cero; es decir, si hay una sola paloma no puede haber conflicto. Para n > m (más palomas que casilleros) es uno, en cuyo caso coincide con el principio de casillero ordinario. Pero incluso si el número de palomas no excede el número de casilleros ( n ≤ m ), debido a la naturaleza aleatoria de la asignación de palomas a los casilleros, a menudo existe una posibilidad sustancial de que se produzcan enfrentamientos. Por ejemplo, si se asignan 2 palomas al azar a 4 casilleros, hay un 25 % de posibilidades de que al menos un casillero contenga más de una paloma; para 5 palomas y 10 hoyos, esa probabilidad es del 69,76%; y para 10 palomas y 20 hoyos es aproximadamente 93,45%. Si el número de hoyos se mantiene fijo, siempre hay una mayor probabilidad de obtener un par cuando agregas más palomas. Este problema se trata con mucho más detalle en la paradoja del cumpleaños .
Una generalización probabilística adicional es que cuando una variable aleatoria de valor real X tiene una media finita E ( X ) , entonces la probabilidad es distinta de cero de que X sea mayor o igual que E ( X ) y, de manera similar, la probabilidad es distinta de cero de que X sea menor o igual a E ( X ) . Para ver que esto implica el principio estándar del casillero, tome cualquier disposición fija de n palomas en m hoyos y sea X el número de palomas en un hoyo elegidas uniformemente al azar. La media de X es n / m , por lo que si hay más palomas que madrigueras la media es mayor que uno. Por lo tanto, X a veces es al menos 2.
El principio del casillero se puede extender a conjuntos infinitos expresándolo en términos de números cardinales : si la cardinalidad del conjunto A es mayor que la cardinalidad del conjunto B , entonces no hay inyección de A a B. Sin embargo, en esta forma el principio es tautológico , ya que el significado de la afirmación de que la cardinalidad del conjunto A es mayor que la cardinalidad del conjunto B es exactamente que no existe una aplicación inyectiva de A a B. Sin embargo, agregar al menos un elemento a un conjunto finito es suficiente para garantizar que la cardinalidad aumente.
Otra forma de expresar el principio de casillero para conjuntos finitos es similar al principio de que los conjuntos finitos son finitos de Dedekind : Sean A y B conjuntos finitos. Si hay una sobreyección de A a B que no es inyectiva, entonces ninguna sobreyección de A a B es inyectiva. De hecho, ninguna función de ningún tipo de A a B es inyectiva. Esto no es cierto para conjuntos infinitos: considere la función de los números naturales que envía 1 y 2 a 1, 3 y 4 a 2, 5 y 6 a 3, y así sucesivamente.
Existe un principio similar para conjuntos infinitos: si se meten incontables palomas en un número contable de casilleros, existirá al menos un casillero que tendrá incontables palomas metidas en él.
Sin embargo, este principio no es una generalización del principio del casillero para conjuntos finitos: en general es falso para conjuntos finitos. En términos técnicos , dice que si A y B son conjuntos finitos tales que cualquier función sobreyectiva de A a B no es inyectiva, entonces existe un elemento b de B tal que existe una biyección entre la preimagen de b y A. Esta es una afirmación bastante diferente y absurda para cardinalidades finitas grandes.
Yakir Aharonov et al. presentó argumentos de que la mecánica cuántica puede violar el principio de casillero y propuso experimentos interferométricos para probar el principio de casillero en la mecánica cuántica. [23] Investigaciones posteriores han puesto en duda esta conclusión. [24] [25] En una preimpresión de arXiv de enero de 2015 , los investigadores Alastair Rae y Ted Forgan de la Universidad de Birmingham realizaron un análisis teórico de la función de onda , empleando el principio de casillero estándar, sobre el vuelo de electrones a diversas energías a través de un interferómetro . Si los electrones no tuvieran ninguna fuerza de interacción, cada uno de ellos produciría un único pico perfectamente circular. Con una fuerza de interacción alta, cada electrón produce cuatro picos distintos, para un total de 12 picos en el detector; Estos picos son el resultado de las cuatro posibles interacciones que cada electrón podría experimentar (solo, junto con la primera partícula únicamente, junto con la segunda partícula únicamente, o las tres juntas). Si la fuerza de interacción fuera bastante baja, como sería el caso en muchos experimentos reales, la desviación de un patrón de interacción cero sería casi imperceptible, mucho menor que el espaciamiento reticular de los átomos en sólidos, como los detectores utilizados para observar estos patrones. Esto haría muy difícil o imposible distinguir una fuerza de interacción débil pero distinta de cero de una interacción nula y, por lo tanto, daría la ilusión de tres electrones que no interactuaron a pesar de que los tres pasaron por dos caminos.
![{\displaystyle \{[na]:n\in \mathbb {Z} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e67b9d01d463917ae8de6dba02f95b073b6e52e1)
![{\displaystyle [na]<{\tfrac {1}{M}}<e,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd14d49dfefbe23c24c1adee5b9a00a1cc42d4d1)
![{\displaystyle [na]<{\tfrac {1}{M}}<e;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1addf70a2612c6298ab272c408ec7fcee36161a7)
![{\displaystyle p\in {\bigl (}0,{\tfrac {1}{M}}{\bigr ]},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52d7f1af69dbce17dfe320f098b0212802320aef)
![{\displaystyle p\in \left({\frac {j}{M}},{\frac {j+1}{M}}\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b77da6d77bb409b557e4a1294afdda442bcc2072)
![{\displaystyle k=\sup \left\{r\in N:r[na]<{\frac {j}{M}}\right\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/337daa7e4adf8a3656e86964302b02ffa2748d26)
![{\displaystyle {\Bigl |}{\bigl [}(k+1)na{\bigr ]}-p{\Bigr |}<{\frac {1}{M}}<e.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3565f263d2e545bfe5d53fa22aa4d5ff821ddd02)
