Principio del casillero

En matemáticas , el principio del palomar establece que si se colocan n elementos en m contenedores, con n > m , entonces al menos un contenedor debe contener más de un elemento. ^[1] Por ejemplo, de tres guantes (ninguno de los cuales es ambidiestro/reversible), al menos dos deben ser diestros o al menos dos deben ser zurdos, porque hay tres objetos pero solo dos categorías de lateralidad para colocarlos. Esta afirmación aparentemente obvia, un tipo de argumento de conteo , se puede utilizar para demostrar resultados posiblemente inesperados. Por ejemplo, dado que la población de Londres es más de una unidad mayor que el número máximo de cabellos que puede haber en la cabeza de un humano, el principio requiere que debe haber al menos dos personas en Londres que tengan el mismo número de cabellos en sus cabezas.

Aunque el principio del casillero aparece ya en 1624 en un libro atribuido a Jean Leurechon , ^[2] se le denomina comúnmente principio de caja de Dirichlet o principio de cajón de Dirichlet después de un tratamiento del principio de 1834 por Peter Gustav Lejeune Dirichlet bajo el nombre de Schubfachprinzip ("principio del cajón" o "principio del estante"). ^[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 palomar 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 suelo y techo , respectivamente.${\displaystyle k+1=\lpiso(n-1)/m\rpiso+1=\lceil n/m\rceil }$${\displaystyle \lfloor \cdots \rfloor}$${\displaystyle \lceil \cdots \rceil }$

Aunque la aplicación más directa del principio es a conjuntos finitos (como palomas y cajas), también se utiliza con conjuntos infinitos que no se pueden poner en correspondencia biunívoca . Para ello se requiere la formulación formal del principio del palomar: "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 tanto el término alemán Schubfach como el francés tiroir . El significado original estricto de estos términos corresponde al inglés drawer , es decir, una caja abierta por arriba que se puede deslizar dentro y fuera del gabinete que la contiene . (Dirichlet escribió sobre la distribución de perlas entre cajones). Estos términos se transformaron en pigeonhole en el sentido de un pequeño espacio abierto en un escritorio, gabinete o pared para guardar cartas o papeles , metafóricamente arraigado en estructuras que albergan palomas.

Dado que los muebles con casilleros se utilizan 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 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, está desapareciendo, especialmente entre aquellos que no hablan inglés como lengua materna, sino como lengua franca en el mundo científico, en favor de la interpretación más pictórica, que involucra literalmente palomas y agujeros. La interpretación sugerente (aunque no engañosa) de "casillero" como " palomar " ha encontrado recientemente su camino de regreso a una traducción inversa 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 en un cajón hay una mezcla de calcetines negros y calcetines azules, cada uno de los cuales se puede usar en cualquier pie. Sacas una cantidad de calcetines del cajón sin mirar. ¿Cuál es la cantidad mínima de calcetines sacados que se requiere para garantizar un par del mismo color? Según el principio del casillero ( m = 2 , utilizando 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 del otro.

Si n personas pueden estrecharse la mano (donde n > 1 ), el principio del casillero muestra que siempre hay un par de personas que estrecharán la mano al mismo número de personas. En esta aplicación del principio, el "agujero" al que se asigna a una persona es el número de manos que esa persona estrecha. Como cada persona estrecha la mano a un número determinado de personas entre 0 y n − 1 , hay n agujeros 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 a todos los demás mientras que otra persona no le da la mano a nadie. Esto deja n personas para ser colocadas en, como máximo, n − 1 agujeros no vacíos, por lo que se aplica 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 . ^[8] Esto se puede ver asociando a cada persona con un vértice y a cada borde con un apretón de manos.

Se puede demostrar que debe haber al menos dos personas en Londres con el mismo número de pelos en sus cabezas de la siguiente manera. ^{[9] [10]} Dado que una cabeza humana típica tiene un promedio de alrededor de 150.000 pelos, es razonable suponer (como límite superior) que nadie tiene más de 1.000.000 de pelos en su 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 elementos). Asignando un casillero a cada número de pelos en la cabeza de una persona, y asignando 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 1.000.001 (porque tienen el mismo número de pelos en sus cabezas; o, n > m ). Suponiendo que Londres tiene 9,002 millones de personas, ^[11] se deduce que al menos diez londinenses tienen la misma cantidad de pelos, ya que tener nueve londinenses en cada uno de los 1 millón de casilleros representa solo 9 millones de personas.

En el caso promedio ( m = 150.000 ) con la restricción: el menor número de superposiciones, habrá como máximo una persona asignada a cada casilla y la persona número 150.001 asignada a la misma casilla que otra persona. En ausencia de esta restricción, puede haber casillas vacías porque la "colisión" ocurre antes de la persona número 150.001. El principio solo prueba la existencia de una superposición; no dice nada sobre el número de superposiciones (que cae dentro del tema de la distribución de probabilidad ).

En inglés, hay una alusión pasajera y satírica a esta versión del principio en A History of the Athenian Society , que precede a A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries (impreso para Andrew Bell, Londres, 1710). ^[12] Parece que la cuestión de si había dos personas en el mundo que tuvieran el mismo número de cabellos en la cabeza se había planteado en The Athenian Mercury antes de 1704. ^{[13] [14]}

Tal vez la primera referencia escrita al principio del palomar 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, escudos u otras cosas que el otro". ^[15] El principio completo fue explicado dos años después, con ejemplos adicionales, en otro libro que a menudo se ha atribuido a Leurechon, pero que podría ser de uno de sus estudiantes. ^[2]

El problema del cumpleaños plantea la 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 ocupa principalmente de probabilidades contraintuitivas, pero también podemos decir mediante el principio del casillero que entre 367 personas, hay al menos un par de personas que comparten el mismo cumpleaños con una probabilidad del 100%, ya que solo hay 366 cumpleaños posibles para elegir.

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 pueden jugar todos en equipos diferentes; debe haber al menos un equipo en el que participen al menos dos de los siete jugadores:

$${\displaystyle \left\lfloor {\frac {n-1}{m}}\right\rfloor +1=\left\lfloor {\frac {7-1}{4}}\right\rfloor +1=\left\lfloor {\frac {6}{4}}\right\rfloor +1=1+1=2}$$

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 los seis "palomas" (elementos del subconjunto de tamaño seis) se colocan en estos casilleros, y cada paloma entra en el casillero que la tiene contenida en su etiqueta, al menos uno de los casilleros etiquetados con un subconjunto de dos elementos tendrá dos palomas en él. ^[16]

En informática, el hash es el proceso de mapear un conjunto arbitrario de datos n a m valores de tamaño fijo. Esto tiene aplicaciones en el almacenamiento en caché , mediante el cual se pueden almacenar grandes conjuntos de datos mediante una referencia a sus valores representativos (sus "códigos hash") en una "tabla hash" para una recuperación rápida. Normalmente, la cantidad de objetos únicos en un conjunto de datos n es mayor que la cantidad de códigos hash únicos disponibles m , y el principio del palomar se cumple en este caso, ya que el hash de esos objetos no es garantía de unicidad, ya que si se aplica el hash a todos los objetos en el conjunto de datos n , algunos objetos necesariamente deben compartir el mismo código hash.

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 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 dada L podría asignarse al conjunto (mucho) más pequeño de todas las secuencias de longitud menor que L sin colisiones (porque la compresión es sin pérdidas), una posibilidad que el principio del palomar excluye.

Un problema notable en el análisis matemático es, para un número irracional fijo a , demostrar que el conjunto ⁠ ⁠${\displaystyle \{[na]:n\in \mathbb {Z} \}}$ de partes fraccionarias es denso en [0, 1] . Se encuentra que no es fácil encontrar explícitamente números enteros n, m tales que donde e > 0 es un número positivo pequeño y a es un número irracional arbitrario. Pero si se toma M tal que ⁠ ⁠ por el principio del palomar debe haber tales que n ₁ a y n ₂ a estén en la misma subdivisión entera de tamaño ⁠ ⁠ (solo hay M subdivisiones de este tipo entre números enteros consecutivos). En particular, se puede encontrar n ₁ , n ₂ tales que${\displaystyle |na-m|<e,}$${\displaystyle {\tfrac {1}{M}}<e,}$${\displaystyle n_{1},n_{2}\en \{1,2,\ldots ,M+1\}}$${\displaystyle {\tfrac {1}{M}}}$

${\displaystyle n_{1}a\in \left(p+{\frac {k}{M}},\ p+{\frac {k+1}{M}}\right),\quad n_{2}a\in \left(q+{\frac {k}{M}},\ q+{\frac {k+1}{M}}\right),}$

para algunos números enteros p, q y k en {0, 1, ..., M − 1 }. Se puede verificar fácilmente que

${\displaystyle (n_{2}-n_{1})a\in \left(q-p-{\frac {1}{M}},q-p+{\frac {1}{M}}\right).}$

Esto implica que ⁠ ⁠${\displaystyle [na]<{\tfrac {1}{M}}<e,}$ donde n = n ₂ − n ₁ o n = n ₁ − n ₂ . Esto muestra que 0 es un punto límite de {[ na ]}. Uno puede entonces usar este hecho para probar el caso para p en (0, 1] : encuentre n tal que ⁠ ⁠${\displaystyle [na]<{\tfrac {1}{M}}<e;}$ entonces si ⁠ ⁠${\displaystyle p\in {\bigl (}0,{\tfrac {1}{M}}{\bigr ]},}$ la prueba está completa. De lo contrario

${\displaystyle p\in \left({\frac {j}{M}},{\frac {j+1}{M}}\right],}$

y estableciendo

${\displaystyle k=\sup \left\{r\in N:r[na]<{\frac {j}{M}}\right\},}$

uno obtiene

${\displaystyle {\Bigl |}{\bigl [}(k+1)na{\bigr ]}-p{\Bigr |}<{\frac {1}{M}}<e.}$

Existen variantes en varias demostraciones. En la demostración 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 recíproco: si se colocan n objetos en k cajas, entonces hay una caja que contiene como máximo ⁠ ⁠${\displaystyle {\tfrac {n}{k}}}$ objetos. ^[19]

Las siguientes son formulaciones alternativas del principio del palomar.

1. Si n objetos se distribuyen en m lugares, y si n > m , entonces algún lugar recibe al menos dos objetos. ^[1]
2. (formulación equivalente de 1) Si n objetos se distribuyen en n lugares de tal manera que ningún lugar recibe más de un objeto, entonces cada lugar recibe exactamente un objeto. ^[1]
3. (generalización de 1) Si S y T son conjuntos, y la cardinalidad de S es mayor que la cardinalidad de T , entonces no hay función inyectiva de S a T .
4. Si n objetos están distribuidos en m lugares, y si n < m , entonces algún lugar no recibe ningún objeto.
5. (formulación equivalente de 4) Si n objetos se distribuyen en n lugares de tal manera que ningún lugar recibe ningún objeto, entonces cada lugar recibe exactamente un objeto. ^[20]
6. (generalización de 4) Si S y T son conjuntos, y la cardinalidad de S es menor que la cardinalidad de T , entonces no existe función sobreyectiva de S a T .

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

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

los objetos se distribuyen en n cajas, entonces la primera caja contiene al menos q ₁ objetos, o la segunda caja contiene al menos q ₂ objetos, ..., o la n- ésima caja contiene al menos q _n objetos. ^[21]

La forma simple se obtiene de esto tomando q ₁ = q ₂ = ... = q _n = 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 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 k objetos discretos se deben asignar a n contenedores, entonces al menos un contenedor debe contener al menos objetos, donde es 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 de objetos, donde es la función piso , que denota el entero más grande menor o igual a x .${\displaystyle \lceil k/n\rceil }$${\displaystyle \lceil x\rceil }$${\displaystyle \lfloor k/n\rfloor }$${\displaystyle \lfloor x\rfloor }$

Una generalización probabilística del principio del palomar establece que si se colocan n palomas al azar en m palomares con una probabilidad uniforme de 1/ m , entonces al menos un palomar contendrá más de una paloma con una 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 m > 0 ), esa probabilidad es cero; en otras palabras, si hay una sola paloma, no puede haber un 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 casilleros a menudo hay una probabilidad sustancial de que ocurran choques. Por ejemplo, si 2 palomas se asignan aleatoriamente a 4 casilleros, hay un 25% de probabilidad de que al menos un casillero contenga más de una paloma; Para 5 palomas y 10 agujeros, esa probabilidad es del 69,76%; y para 10 palomas y 20 agujeros es de alrededor del 93,45%. Si el número de agujeros permanece fijo, siempre hay una mayor probabilidad de que se forme un par cuando se añaden más palomas. Este problema se trata con mucha más 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 es distinta de cero de que X sea mayor o igual a 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 agujeros y sea X el número de palomas en un agujero elegido uniformemente al azar. La media de X es n / m , por lo que si hay más palomas que agujeros la media es mayor que uno. Por lo tanto, X es a veces al menos 2.

El principio del palomar se puede extender a conjuntos infinitos al formularlo 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 hay una función inyectiva de A a B. Sin embargo, agregar al menos un elemento a un conjunto finito es suficiente para garantizar que la cardinalidad aumenta.

Otra forma de expresar el principio del palomar 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 sea 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 en 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.

Hay un principio similar para los conjuntos infinitos: si se meten un número incontable de palomas en un número contable de casilleros, existirá al menos un casillero que contenga un número incontable de palomas.

Sin embargo, este principio no es una generalización del principio del palomar 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 es absurda para cardinalidades finitas grandes.

Yakir Aharonov et al. presentaron argumentos de que la mecánica cuántica puede violar el principio del palomar, y propusieron experimentos interferométricos para probar el principio del palomar en la mecánica cuántica. ^[23] Investigaciones posteriores han puesto en tela de juicio 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 del palomar estándar, en 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 primera otra partícula solamente, junto con la segunda otra partícula solamente, o los tres juntos). 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 los 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 no nula de una interacción nula en absoluto, y daría así la ilusión de tres electrones que no interactuaran a pesar de que los tres pasaran por dos caminos.

• Axioma de elección
• Teorema de Blichfeldt
• Principios combinatorios
• Prueba combinatoria
• Conjunto infinito de Dedekind
• Teorema de aproximación de Dirichlet
• La paradoja de Hilbert del Grand Hotel
• Teorema multinomial
• Símbolo del martillo perforador
• Teorema de Ramsey

• Brualdi, Richard A. (2010), Combinatoria introductoria (5.ª ed.), Pentice Hall, ISBN 978-0-13-602040-0
• Fletcher, Peter; Patty, C. Wayne (1987), Fundamentos de matemáticas superiores , PWS-Kent, ISBN 978-0-87150-164-6
• Grimaldi, Ralph P. (1994), Matemáticas discretas y combinatorias: una introducción aplicada (3.ª ed.), Addison-Wesley, ISBN 978-0-201-54983-6
• Herstein, IN (1964), Temas de álgebra , Waltham: Blaisdell Publishing Company, ISBN 978-1114541016

Escuche este artículo ( 24 minutos )

Este archivo de audio se creó a partir de una revisión de este artículo con fecha del 5 de junio de 2021 y no refleja ediciones posteriores. (2021-06-05)

( Ayuda de audio  · Más artículos hablados )

• "Principio de la caja de Dirichlet", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• "El extraño caso del principio del palomar"; Edsger Dijkstra investiga interpretaciones y reformulaciones de este principio.
• "El principio del palomar"; ejemplos elementales del principio en uso por Larry Cusick.
• "Principio del palomar de Miscelánea y rompecabezas de matemáticas interactivas"; análisis básico del principio del palomar y ejemplos por Alexander Bogomolny .
• "16 aplicaciones divertidas del principio del palomar"; Datos interesantes derivados del principio.
• "¿Cuántos humanos tienen la misma cantidad de pelos en el cuerpo?". PBS Infinite Series . 1 de diciembre de 2016. Archivado desde el original el 11 de diciembre de 2021 – vía YouTube .