Principio del casillero

Pigeones en agujeros. Aquí hay n = 10 palomas en m = 9 agujeros. Dado que 10 es mayor que 9, el principio de la paloma dice que al menos un agujero tiene más de una paloma. (El agujero superior izquierdo tiene 2 palomas.)

En matemáticas, el principio del casillero establece que si n elementos se colocan en m contenedores, con n > m, al menos un contenedor debe contener más de un elemento. Por ejemplo, si uno tiene tres guantes (y ninguno es ambidiestro/reversible), entonces debe haber al menos dos guantes para diestros, o al menos dos guantes para zurdos, porque hay tres objetos, pero solo dos categorías de destreza manual. para meterlos. Esta declaració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 pueden estar presentes en la cabeza de un ser humano, entonces el principio del casillero requiere que debe haber al menos dos personas en Londres que tengan el mismo número de pelos en sus cabezas.

Aunque el principio del casillero aparece ya en 1624 en un libro atribuido a Jean Leurechon, comúnmente se le llama principio de la caja de Dirichlet o principio del cajón de Dirichlet< /b> después de un tratamiento de 1834 del principio por Peter Gustav Lejeune Dirichlet bajo el nombre Schubfachprinzip ("principio de cajón" o "principio de estante").

El principio tiene varias generalizaciones y se puede decir de diversas maneras. En una versión más cuantificada: para números naturales k y m, si n = km + 1 los objetos se distribuyen entre m sets, entonces el principio de la paloma afirma que al menos uno de los conjuntos contendrá al menos k + 1 objetos. Para arbitrarios n y m, esto se generaliza a ${displaystyle k+1=lfloor (n-1)/mrfloor +1=lceil n/mrceil}$ Donde ${displaystyle lfloor cdots rfloor }$ y ${displaystyle lceil cdots rceil }$ denota las funciones de piso y techo, respectivamente.

Aunque la aplicación más sencilla es para conjuntos finitos (como palomas y cajas), también se usa con conjuntos infinitos que no se pueden poner en correspondencia uno a uno. Para ello se requiere el enunciado formal del principio del casillero, que es "no existe una función inyectiva cuyo codominio sea menor que su dominio". Las pruebas matemáticas avanzadas como el lema de Siegel se basan en este concepto más general.

Etimología

Cajas de mensajes en la Universidad de Stanford

Dirichlet publicó sus obras tanto en francés como en alemán, usando el alemán Schubfach o el francés tiroir. El sentido original estricto de estos términos corresponde al cajón inglés, es decir, una caja abierta por la parte superior que se puede deslizar dentro y fuera del gabinete que la contiene. (Dirichlet escribió sobre la distribución de perlas entre los cajones). Estos términos se transformaron en la palabra casillero en el sentido de un pequeño espacio abierto en un escritorio, armario o pared para guardar cartas o papeles< /i>, metafóricamente enraizado 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 casillero puede ser una mejor representación de La metáfora 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 la interpretación más pictórica, literalmente involucrando palomas y agujeros. La interpretación sugerente (aunque no engañosa) de "casillero" como "palomar" ha encontrado recientemente su camino de regreso a una retrotraducción alemana del "principio del casillero" como el "Taubenschlagprinzip".

Además de los términos originales "Schubfachprinzip" en alemán y "Principe des tiroirs" en francés, todavía se usan otras traducciones literales en árabe ("مبدأ برج الحمام"), búlgaro ("принцип на чекмеджетата"), chino ("抽屉原理"), danés ("Skuffeprincippet"), holandés ("ladenprincipe"), húngaro ("skatulyaelv "), italiano ("principio dei cassetti"), japonés ("引き出し論法"), persa ("< span title="Texto en idioma persa">اصل لانه کبوتری"), polaco ("zasada szufladkowa"), portugués ("Princípio das Gavetas"), sueco ("Lådprincipen"), turco ("çekmece ilkesi") y vietnamita ("nguyên lý hộp").

Ejemplos

Recogida de calcetines

Suponga que un cajón contiene una mezcla de calcetines negros y calcetines azules, cada uno de los cuales se puede usar en cualquier pie, y que está sacando varios calcetines del cajón sin mirar. ¿Cuál es el número mínimo de calcetines tirados necesarios para garantizar un par del mismo color? Usando el principio del casillero (m = 2 calcetines, usando un casillero por color), necesitas sacar solo tres calcetines del cajón (n = 3 elementos). O tienes tres de un color, o tienes dos de un color y uno del otro.

Apretón de manos

Si hay n personas que pueden darse la mano (donde n > 1), el principio del casillero 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 'agujero' a la que se asigna una persona es el número de manos estrechadas por esa persona. Dado que cada persona da la mano a un número de personas de 0 a n − 1, hay n posibles agujeros. Por otro lado, ya sea el '0' o el 'n − 1' o ambos deben estar vacíos, ya que es imposible (si n > 1) para que una persona le dé la mano a todos los demás mientras que otra persona no le da la mano a nadie. Esto deja n personas para ubicar como máximo n − 1 agujeros no vacíos, para que se aplique el principio.

Este ejemplo de apretón de manos es equivalente 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. Esto se puede ver asociando cada persona con un vértice y cada arista con un apretón de manos.

Conteo de cabello

Se puede demostrar que debe haber al menos dos personas en Londres con el mismo número de cabellos en la cabeza de la siguiente manera. 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 más grande que 1 millón de artículos). Asignando un casillero a cada número de cabellos en la cabeza de una persona, y asignando personas a casilleros según el número de cabellos en su cabeza, debe haber al menos dos personas asignadas al mismo casillero por la asignación 1,000,001 (porque tienen el mismo número de cabellos en la cabeza) (o, n > m). Asumiendo que Londres tiene 9.002 millones de personas, incluso se puede afirmar que al menos diez londinenses tienen la misma cantidad de cabellos, ya que tener nueve londinenses en cada uno de los 1 millón de casilleros representa solo 9 millones de personas.

Para el caso promedio (m = 150,000) con la restricción: la menor cantidad de superposiciones, habrá como máximo una persona asignada a cada casillero y la persona número 150.001 asignada al mismo casillero que otra persona. En ausencia de esta restricción, puede haber casilleros vacíos porque la "colisión" sucede antes de la persona 150,001. El principio simplemente prueba la existencia de una superposición; no dice nada del número de superposiciones (que cae dentro del tema de la 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, con el prefijo "A Supplement to the Athenian Oracle: Being a Collection de El Preguntas y respuestas restantes en el Old Athenian Mercuries", (Impreso para Andrew Bell, Londres, 1710). Parece que la pregunta si había dos personas en el mundo que tuvieran el mismo número de cabellos en la cabeza? se planteó en El mercurio ateniense antes de 1704.

Quizás la primera referencia escrita al principio del casillero aparece en 1622 en una breve frase de la obra latina Selectæ Propositiones, del jesuita francés Jean Leurechon, donde escribió "Es necesario que dos hombres tienen la misma cantidad de cabellos, écus u otras cosas, como cada uno." 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 puede haber sido escrito por uno de sus alumnos.

El problema del cumpleaños

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í se relaciona principalmente con probabilidades contrarias a la intuición; sin embargo, 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 un 100% de probabilidad, ya que solo hay 366 cumpleaños posibles para elegir (incluido el 29 de febrero, si está presente).

Torneo por equipos

Imagínese siete personas que quieren jugar en un torneo de equipos (n = 7 elementos), con una limitación de solo cuatro equipos (m = 4 agujeros) para elegir. El principio del casillero nos dice que no todos pueden jugar en diferentes equipos; debe haber al menos un equipo con al menos dos de los siete jugadores:

$${displaystyle leftlfloor {frac {n-1}{m}rightrfloor +1=leftlfloor {frac {7-1}{4}rightrfloor +1=leftlfloor {frac {6}{4}rightrfloor +1=1+1=2}$$

Suma de subconjunto

Cualquier subconjunto de tamaño seis del conjunto S = {1,2,3,...,9} debe contener dos elementos cuyos la suma es 10. Los casilleros se etiquetarán con 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 de tamaño seis) se colocan en estos casilleros, cada casillero entra 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 casilleros en él.

Usos y aplicaciones

El principio se puede utilizar para demostrar que cualquier algoritmo de compresión sin pérdidas, siempre que haga que algunas entradas sean más pequeñas (como sugiere el nombre 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 asignarse al conjunto (mucho) más pequeño de todas las secuencias de longitud inferior a L sin colisiones (porque la compresión no tiene pérdidas), una posibilidad que excluye el principio del casillero.

Un problema notable en el análisis matemático es, para un número irracional fijo a, mostrar que el conjunto {[na]: n es un número entero} de partes fraccionarias es denso en [0, 1]. Uno encuentra que no es fácil encontrar explícitamente números enteros n, m tales que |na − m| < e, donde e > 0 es un pequeño número positivo y a es un número irracional arbitrario. Pero si uno toma M tal que 1/M < e, según el principio del casillero, debe haber n₁, n< /i>₂ ∈ {1, 2,..., M + 1} tal que n ₁a y n₂< i>a están en la misma subdivisión de enteros de tamaño 1/M (solo hay M tales subdivisiones entre enteros consecutivos). En particular, uno puede encontrar n₁, n₂ tal que n₁a está en (p + k/M, p + (k + 1)/< i>M) y n₂a está en (q + k/M, q + (k + 1)/M), para algunos p, q enteros y k en {0, 1,..., M< /i> − 1}. Entonces se puede verificar fácilmente que (n₂ − n₁)< i>a está en (q − p − 1/M, q − p + 1/M). Esto implica que [na] < 1/M < e, donde n = n₂ − n₁ o n = n_{1 − n2}. 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]: encuentra n tal que [na] < 1/M< /i> < e; entonces si p ∈ (0, 1/M ], la demostración está completa. De lo contrario, p ∈ (j/M, (< i>j + 1)/M], y configurando k = sup{ r ∈ N: r[na] j/M}, se obtiene |[(k + 1)na] − p | < 1/M < e.

Las variantes ocurren en varias pruebas. En la prueba del lema de bombeo para lenguajes regulares, se usa una versión que mezcla conjuntos finitos e infinitos: si se colocan una cantidad infinita de objetos en un número finito de cajas, entonces existen dos objetos que comparten una caja. En la solución de Fisk al problema de la galería de arte, se usa una especie de inversa: si se colocan n objetos en k cajas, entonces hay una caja que contiene como máximo n/k objetos.

Fórmulas alternativas

Las siguientes son formulaciones alternativas del principio del casillero.

1. Si n objetos se distribuyen m lugares, y si n ■ m, entonces algún lugar recibe al menos dos objetos.
2. (equivalente formulación de 1) Si n objetos se distribuyen n lugares de tal manera que ningún lugar recibe más de un objeto, entonces cada lugar recibe exactamente un objeto.
3. Si n objetos se distribuyen m lugares, y si n. m, entonces algún lugar no recibe ningún objeto.
4. (Formulación equivalente de 3) Si n objetos se distribuyen n lugares de tal manera que ningún lugar recibe ningún objeto, entonces cada lugar recibe exactamente un objeto.

Forma fuerte

Sean q₁, q₂,..., q_n sean números enteros positivos. Si

${displaystyle q_{1}+q_{2}+cdots +q_{n}-n+1}$

los objetos se distribuyen en n cuadros, entonces el primer cuadro contiene al menos q< /i>₁ objetos, o el segundo cuadro contiene al menos q₂ objetos,..., o el nésimo cuadro contiene al menos q_n objetos.

La forma simple se obtiene tomando q₁ = q_{2< /sub> =... = qn = 2}, lo que da n + 1 objetos. Tomando q₁ = q₂ =... = q_n = r da la versión más cuantificada del principio, a saber:

Sean n y r números enteros positivos. Si n(r - 1) + 1 los objetos se distribuyen en n cuadros, al menos uno de los cuadros contiene r o más de los objetos.

Esto también se puede decir como: k se asignarán objetos discretos n contenedores, entonces al menos un contenedor debe mantener al menos ${displaystyle lceil k/nrceil }$ objetos, donde ${displaystyle lceil xrceil }$ es la función del techo, denotando el entero más pequeño más grande o igual a x. Del mismo modo, al menos un contenedor no debe contener más que ${displaystyle lfloor k/nrfloor }$ objetos, donde ${displaystyle lfloor xrfloor }$ es la función del suelo, denotando el entero más grande menor o igual a x.

Generalizaciones del principio del casillero

Una generalización probabilística del principio del casillero establece que si n las palomas se colocan aleatoriamente en m casilleros con probabilidad uniforme 1/m, entonces al menos un casillero albergará más de una paloma con probabilidad

${displaystyle 1-{frac {(m)_{n} {m^{n}}}$

donde (m)_n es el factorial descendente m(m − 1)(m − 2)...(m − n + 1). Para n = 0 y para n = 1 (y < span class="texhtml">m > 0), esa probabilidad es cero; en otras palabras, 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 del casillero ordinario. Pero incluso si el número de palomas no excede el número de casilleros (n ≤ m), debido al azar naturaleza de la asignación de palomas a casilleros, a menudo existe una posibilidad sustancial de que se produzcan conflictos. Por ejemplo, si se asignan aleatoriamente 2 palomas 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 huecos, esa probabilidad es del 69,76%; y para 10 palomas y 20 agujeros es del 93,45%. Si el número de hoyos se mantiene fijo, siempre hay una mayor probabilidad de un par cuando agrega más palomas. Este problema se trata con mucha mayor extensión en la paradoja del cumpleaños.

Otra generalización probabilística es que cuando una variable aleatoria de valor real X tiene una media finita E(X), entonces la probabilidad de que X sea mayor que o igual a E(X), y de manera similar la probabilidad es distinta de cero de que < i>X es menor o igual que E(X). Para ver que esto implica el principio estándar del casillero, tome cualquier disposición fija de n palomas en m< /i> agujeros y sea X el número de palomas en un agujero elegido uniformemente al azar. La media de X es n/m< /span>, por lo que si hay más palomas que hoyos, la media es mayor que uno. Por lo tanto, X a veces es al menos 2.

Conjuntos infinitos

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 desde A a B. Sin embargo, de 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 hay un mapa inyectivo de A a B. Sin embargo, agregar al menos un elemento a un conjunto finito es suficiente para asegurar que la cardinalidad aumente.

Otra forma de expresar el principio del casillero para conjuntos finitos es similar al principio de que los conjuntos finitos son finitos de Dedekind: Sea A y B sean conjuntos finitos. Si hay una sobreyección de A a B que no es inyectiva, entonces no hay sobreyección de A a B es inyectivo. De hecho, ninguna función de ningún tipo desde A hasta B es inyectivo. 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 introducen incontables palomas en innumerables casilleros, existirá al menos un casillero con 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 desde A hasta 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 declaración bastante diferente y es absurda para grandes cardinalidades finitas.

Mecánica cuántica

Yakir Aharonov et al. han presentado argumentos de que el principio del casillero puede violarse en la mecánica cuántica y han propuesto experimentos interferométricos para probar el principio del casillero en la mecánica cuántica. Sin embargo, investigaciones posteriores han puesto en duda esta conclusión. 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 estándar del casillero, sobre el vuelo de electrones a varias energías a través de un interferómetro. Si los electrones no tuvieran ninguna fuerza de interacción, cada uno 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 interacciones posibles que cada electrón podría experimentar (solo, junto con la otra partícula solamente, junto con la otra partícula solamente, o los tres juntos). Si la fuerza de la 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 más pequeña que el espacio reticular de los átomos en los sólidos, como los detectores que se usan para observar estos patrones. Esto haría muy difícil o incluso imposible distinguir una fuerza de interacción débil pero distinta de cero de ninguna interacción 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.