Principio de Dirichlet (combinatoria)

El principio de Dirichlet es un método simple, intuitivo y a menudo útil para probar afirmaciones de conjuntos finitos . Este principio se usa a menudo en matemáticas discretas , donde establece una conexión entre objetos ("conejos") y contenedores ("células") bajo ciertas condiciones [1] . En inglés y algunos otros idiomas, esta declaración se conoce como el principio del casillero , cuando los objetos son palomas y los contenedores son cajas [ 2] .

La más común es la formulación más simple del principio de Dirichlet [3] :

Si los conejos están sentados en jaulas y el número de conejos es mayor que el número de jaulas, entonces al menos una de las jaulas contiene más de un conejo.

También hay una expresión común para ello:

Si el número de celdas es mayor que el número de conejos, al menos una celda está vacía.

Para otras formulaciones más generales, consulte a continuación .

Los historiadores encontraron la primera formulación de este principio en la popular colección Récréations Mathématiques ( Récréations Mathématiques en francés , 1624, bajo el nombre de H. van Etten ), que fue publicada (presuntamente) por el matemático francés Jean Leurechon [4] . Este principio se generalizó después de su aplicación por Dirichlet (a partir de 1834) en el campo de la teoría de números [5] .

El principio de Dirichlet, de una forma u otra, se aplica con éxito en la demostración de teoremas, lo que hace que estas demostraciones sean más simples y claras. Entre sus áreas de aplicación se encuentran las [6], etc.de sistemas de desigualdades lineales, el análisis de la solucionabilidadlas aproximaciones diofánticasmatemáticas discretas, la teoría [3] .

Otra redacción

Prueba

El principio de Dirichlet en la formulación más simple: " si el número de conejos es mayor que el número de células, entonces al menos una de las células contiene más de un conejo " puede probarse mediante el método "por contradicción" . Que haya jaulas y conejos, además . Denotar. el número de conejos en la -ésima celda ( ). Suponga que hay como máximo un conejo en cada jaula: $norte$ $metro$ ${\ estilo de visualización m> n}$ $k_i$ $i$ ${\ estilo de visualización i = 1,2, \ puntos n}$

$k_{1}\leqslant 1$ (el número de conejos en la 1ra jaula es menor o igual a 1);
$k_{2}\leqslant 1$ (el número de conejos en la 2ª jaula es menor o igual a 1);
...
$k_{n}\leqslant1$ (el número de conejos en la -ésima celda es menor o igual a 1). $norte$

Entonces el número total de conejos Por lo tanto Pero según la condición del problema . Tengo una contradicción, ■ . $m=k_{1}+k_{2}+\ldots +k_{n}\leqslant 1+1+\ldots +1=n.$ $m\leqslant n$ ${\ estilo de visualización m> n}$

La declaración de pares se prueba de manera similar: " si el número de celdas es mayor que el número de conejos, entonces al menos una celda está vacía ".

Además de las dos formulaciones anteriores, hay dos más útiles, que también se prueban fácilmente [7] :

Si los conejos están sentados en jaulas y no hay jaulas vacías, entonces hay exactamente un conejo en cada jaula. $norte$ $norte$
Si los conejos se colocan en jaulas y ninguna jaula contiene más de un conejo, entonces hay exactamente un conejo en cada jaula. $norte$ $norte$

Opciones para formulaciones más generales [8] :

Con cualquier distribución o más de artículos en cajas, en cualquier caja no habrá menos de un artículo. ${\ estilo de visualización kn+1}$ $norte$ $k+1$
Si los conejos están sentados en jaulas, entonces al menos una jaula contiene al menos conejos y al menos una jaula no contiene más que conejos. Aquí , las esquinas de Iverson y redondean la expresión encerrada en ellas al todo, respectivamente, arriba y abajo. $metro$ $norte$ $\left\lceil {\frac {m}{n}}\right\rceil$ $\left\lpiso {\frac {m}{n}}\right\rpiso$ ${\ estilo de visualización \ lceil \ puntos \ rceil}$ ${\ estilo de visualización \ lpiso \ puntos \ rpiso}$
Sea dada una función definida en un conjunto finito y mapeándola a un conjunto finito : donde es algún número natural , y la construcción de la forma significa el número de elementos del conjunto finito ( la cardinalidad del conjunto ). Entonces la función tomará algún valor al menos una vez. $F,$ $A$ $B$ $f\dos puntos A\rightarrow B,$ $\left|A\right|>n\cdot \left|B\right|,$ $norte$ ${\ estilo de visualización \ izquierda | X \ derecha |}$ $X$ $F$ $n+1$

Ejemplos de aplicación

Teorema 1 . Para cualquier elección de cinco puntos dentro del cuadrado unitario , hay un par de puntos separados entre sí por no más de ${\frac {\sqrt {2}}{2}}.$

prueba _ El teorema a primera vista parece complicado y no obvio, pero con la ayuda del principio de Dirichlet se demuestra sin dificultad [9] . Divide el cuadrado en 4 cuartos, como se muestra en la figura. De acuerdo con el principio de Dirichlet, al menos dos de los cinco puntos seleccionados caerán en un cuarto, y entonces la distancia entre ellos no será mayor que la diagonal del cuarto, igual a ■ ${\sqrt {{\left({\frac {1}{2}}\right)}^{2}+{\left({\frac {1}{2}}\right)}^{ 2}}}={\frac{\sqrt {2}}{2}}.$

Teorema 2 . Parte de la compañía de personas se dan la mano. Demostrar que hay al menos dos personas en la empresa que han hecho el mismo número de apretones de manos [10] . $norte$ ${\ estilo de visualización \ izquierda (N> 1 \ derecha)}$

prueba _ Vamos - "cajas". Pongamos en el casillero a aquellos miembros de la empresa que se dieron la mano. Si la casilla no está vacía, entonces uno o más miembros de la empresa no han hecho ningún apretón de manos y, por lo tanto, la casilla está vacía, porque el número de apretones de manos es entonces menor . Se deduce que siempre hay menos no vacíos. cajas que y, por lo tanto, al menos una caja corresponde a dos o más personas. ■ $\{H_{0},H_{1},\puntos H_{N-1}\}$ $norte$ $H_{k}$ $k$ $H_{0}$ $H_{N-1}$ ${\ estilo de visualización N.}$ ${\ estilo de visualización N,}$

Teorema 3 . Para cualquier número irracional positivo , hay infinitas fracciones que difieren de menos de por (esta es una de las versiones del teorema de Dirichlet sobre aproximaciones diofánticas ) [11] [12] . $a$ ${\frac{p}{q)),$ $a$ ${\ Displaystyle {\ frac {1} {q^ {2}}}}$

prueba _ Para un número natural arbitrario , hagamos un conjunto de valores: $norte$ ${\ estilo de visualización (N+1)}$

d_{1}=1\cdot a-[1\cdot a],

d_{2}=2\cdot a-[2\cdot a],

d_{3}=3\cdot a-[3\cdot a],

\ puntos ,

d_{N+1}=(N+1)\cdot a-[(N+1)\cdot a],

donde denota la parte entera de un número.

[X]

Todos estos números pertenecen al intervalo de 0 a 1 inclusive. Los distribuimos en cuadros: en el primer cuadro ponemos números de 0 inclusive a no inclusivo, en el segundo - de inclusivo a no inclusivo, etc., en el th - de inclusivo a no inclusivo. Pero como el número de números es mayor que el número de casillas, entonces, según el principio de Dirichlet, en una de las casillas habrá al menos dos diferencias: y cuando $norte$ ${\ estilo de visualización 1/N}$ ${\ estilo de visualización 1/N}$ ${\ estilo de visualización 2/N}$ $norte$ ${\ estilo de visualización (N-1)/N}$ ${\ estilo de visualización N/N}$ ${\ estilo de visualización \ izquierda (N + 1 \ derecha)}$ ${\ estilo de visualización \ izquierda (N \ derecha),}$ $d_{i}=\left(i\cdot a-[i\cdot a]\right)$ $d_{j}=\left(j\cdot a-[j\cdot a]\right)$ ${\ estilo de visualización i<j.}$

Los valores de las diferencias por construcción difieren en menos que Suponiendo y obtenemos: ${\frac{1}{N}}:$ $d_{j}-d_{i}<{\frac {1}{N)).$ ${\ estilo de visualización q = ji}$ $p=[j\cdot a]-[i\cdot a],$

|q\cdot ap|<{\frac{1}{N)),

o: (porque ).

\left|a-{\frac {p}{q}}\right|<{\frac {1}{q\cdot N}}\leqslant {\frac {1}{q^{2}} }

q\leqslant N

Debido a la arbitrariedad del número, la proximidad de una fracción a un número puede hacerse arbitrariamente pequeña (en este caso, ciertamente es distinta de cero, ya que es irracional por condición). Por lo tanto, el número de fracciones correspondientes a aproximaciones cada vez más cercanas es infinito. ■ $norte$ $p/q$ $a$ $a$ ${\frac{p}{q)),$

Se pueden encontrar ejemplos adicionales en las siguientes fuentes.

Artículo Teorema del resto chino .
Libro de N. B. Alfutova y A. V. Ustinov [13] .
Libro M. Aigner M. y G. Ziegler [14] .
Libro de A. A. Andreev y otros [15]

Aplicaciones geométricas

En geometría se utilizan varias variantes del principio de Dirichlet, relativas a longitudes, áreas y volúmenes [16] .

Si en un segmento de longitud hay varios segmentos con una suma de longitudes mayor que , entonces al menos dos de estos segmentos tienen un punto común. $L$ $L$
Generalización . Si hay varios segmentos en un segmento de longitud cuya suma de longitudes es mayor que , entonces al menos un punto está cubierto por al menos uno de estos segmentos. $L$ ${\ Displaystyle kL}$ $k+1$
Si la suma de las longitudes de los segmentos es menor que , entonces no pueden cubrir completamente el segmento de longitud . $L$ $L$
Si hay varias figuras dentro de la figura de un área cuya suma de áreas es mayor que , entonces al menos dos de ellas tienen un punto en común. $S$ $S$
Si la suma de las áreas de varias figuras es menor , entonces no pueden cubrir la figura del área . $S$ $S$

Se pueden formular enunciados similares para volúmenes.

Ejemplo [17] . Varios círculos se colocan aleatoriamente en un círculo de diámetro 6, la suma de sus diámetros es igual a 50. Demuestra que hay una línea que corta al menos nueve de estos círculos.

prueba _ Sea un diámetro arbitrario del círculo original (de longitud 6). Proyectemos todos los círculos interiores a un diámetro de . La suma de las longitudes de las proyecciones es obviamente igual a la suma de los diámetros de los círculos, es decir, 50, y cubren (no necesariamente por completo) el diámetro . Dado que , entonces, según la 2ª versión del principio de Dirichlet, existe un punto en el segmento AB que pertenece a las proyecciones de al menos nueve circunferencias. Entonces la línea que pasa por este punto y es perpendicular al diámetro es la requerida, intersecta todos estos nueve círculos. ■ $D$ $D$ $D$ $50>8\cdot D$ $D$

Variaciones y generalizaciones

Una forma de generalizar el principio de Dirichlet lo extiende a los números reales [18] .

Si los conejos comieron un kg de hierba, entonces al menos un conejo comió al menos un kg de hierba. $metro$ $norte$ ${\ estilo de visualización n \ sobre m}$

Consecuencias [18] .

Si la suma de los números es mayor entonces al menos uno de estos números es mayor $norte$ $S$ ${\frac{S}{n}}.$
Si la media aritmética de varios números es mayor que , entonces al menos uno de estos números es mayor $A$ $UNA.$

Hay una generalización del principio de Dirichlet al caso de conjuntos infinitos : no hay inyección de un conjunto más poderoso en uno menos poderoso [19] .

Ejemplos [19] .

Si hay un número infinito de palomas en un conjunto finito de celdas, entonces al menos una celda contendrá más de una paloma. Además, es fácil demostrar que habrá un número infinito de palomas en al menos una celda.
Si un conjunto incontable de palomas está contenido en un conjunto contable de cajas, entonces al menos una celda contendrá más de una paloma. Además, se puede demostrar que habrá un número incontable de palomas en al menos una celda.

La generalización anterior se basa, por ejemplo, en la demostración del lema de Siegel propuesta por Axel Thue [20] .

En el artículo Teoría de Ramsey se dan varias generalizaciones modernas del principio de Dirichlet .

Principio probabilístico de Dirichlet. Suponga que los conejos están sentados en jaulas aleatorias y los conejos están sentados en jaulas aleatorias de las mismas jaulas. Denote por la probabilidad de que un conejo con un conejo esté sentado en alguna jaula.

metro

k

norte

k

{\ estilo de visualización p (m, n, k)}

Si para algunos fijos , entonces para .

m\cdot n>k^{1+\varepsilon}

\varepsilon >0

{\ estilo de visualización p (m, n, k) \ a 1}

k\to\infty

Si para algunos fijos , entonces para .

{\displaystyle m\cdot n<k^{1-\varepsilon))

\varepsilon >0

{\ estilo de visualización p (m, n, k) \ a 0}

k\to\infty

Notas

↑ Andreev et al., 1997 , pág. 3.
↑ En alemán, la afirmación se denomina "principio de la caja" ( alemán: schubfachprinzip )
↑ 1 2 Uspensky, V. A. Prefacio a las matemáticas [colección de artículos]. - San Petersburgo. : LLC "Casa comercial y editorial Amphora", 2015. - S. 336-338. — 474 pág. — (Ciencia Popular, n. 12). - ISBN 978-5-367-03606-0 .
↑ Rittaud, Benoît; Heeffer, Albrecht (2014). “El principio del casillero, dos siglos antes de Dirichlet” . El Inteligencia Matemática . 36 (2):27-29. DOI : 10.1007/s00283-013-9389-1 . HDL : 1854/LU-411526 . MR 3207654 . Archivado desde el original el 25 de diciembre de 2021 . Consultado el 01-10-2021 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ Jeff Miller, Peter Flor, Gunnar Berg, Julio González Cabillon . Principio del casillero. Archivado el 12 de febrero de 2010 en Wayback Machine . // Jeff Miller (ed.) Primeros usos conocidos de algunas de las palabras de las matemáticas . Archivado el 4 de marzo de 2009 en Wayback Machine . Documento electrónico, consultado el 11 de noviembre de 2006
↑ Enciclopedia Mat., 1982 .
↑ Brualdi, Richard A. (2010), Combinatoria introductoria (5.ª ed.), Prentice Hall , p. 70, ISBN 978-0-13-602040-0
↑ Alfutova N. B., Ustinov A. V., 2009 , pág. 17
↑ Rue, Juanjo. Eterno vagabundo // El arte de contar. Combinatoria y enumeración (Capítulo 3). - M. : De Agostini, 2014. - S. 87. - 144 p. — (El Mundo de las Matemáticas: en 45 tomos, tomo 34). - ISBN 978-5-9774-0729-8 .
↑ Foxford .
↑ Durán, Antonio. Poesía de números. Bien y matemáticas. - M. : De Agostini, 2014. - S. 57. - 160 p. — (El Mundo de las Matemáticas: en 45 volúmenes, volumen 27). — ISBN 978-5-9774-0722-9 .
↑ Alfutova N. B., Ustinov A. V., 2009 , pág. 19
↑ Alfutova N. B., Ustinov A. V., 2009 , pág. 17-20.
↑ Aigner, Ziegler, 2006 .
↑ Andreev et al., 1997 .
↑ Andreev et al., 1997 , pág. 13-16.
↑ Andreev et al., 1997 , pág. catorce.
↑ 1 2 Andreev et al., 1997 , pág. 16-18.
↑ 12 Francisco Su . Principio del casillero . Consultado el 3 de octubre de 2021. Archivado desde el original el 3 de octubre de 2021. (indefinido)
↑ Jueves , A. (1909), Über Annäherungswerte algebraischer Zahlen , Journal für die reine und angewandte Mathematik T. 1909 (135): 284–305, ISSN 0075-4102 , doi : 10.1515/crll.1909.135.284 , < http://resolver.sub .uni-goettingen.de/purl?PPN243919689_0135 > Archivado el 30 de octubre de 2020 en Wayback Machine .

Literatura

Aigner M. , Ziegler G. El principio de Dirichlet y la doble contabilidad () capítulo 22) // Pruebas del libro . La mejor evidencia desde la época de Euclides hasta nuestros días. — M .: Mir, 2006. — 256 p. — ISBN 5-03-003690-3 .
Alfutova N. B., Ustinov A. V. Álgebra y teoría de números. Colección de tareas para escuelas de matemáticas. - 3ra ed., rev. agregar.. - M. : MTSNMO, 2009. - 336 p. - ISBN 978-5-94057-550-4 .
Andreev A. A., Gorelov G. N., Lyulev A. I., Savin A. N. El principio de Dirichlet. Edición educativa. - Samara: Pitágoras, 1997. - 21 p. - (Serie A: Matemáticas. Número 1).
Glibichuk A. A., Dainyak A. B., Ilyinsky D. G., Kupavsky A. B., Raigorodsky A. M., Skopenkov A. B., Chernov A. A. Elementos de matemáticas discretas en problemas. - M. : MTSNMO, 2016. - S. 12-14. — 174 pág. — ISBN 978-5-4439-3024-4 .
Principio de Dirichlet, recuadros // Enciclopedia Matemática (en 5 tomos). - M .: Enciclopedia soviética , 1982. - T. 2. - S. 182.
Znak E. I. Particiones de celosías enteras y el principio de Dirichlet // Educación matemática . - 2015. - Edición. 19 (tercera serie) . - S. 241-248 .

Enlaces

Boltyansky V. Seis liebres en cinco jaulas // Kvant . - 1977. - N° 2. - S. 17-20, 37, 42.
Bugaenko V. O. Círculo matemático. Grado 9 Lección número 2. Principio de Dirichlet . Fecha de acceso: 18 de noviembre de 2020. (indefinido)
Principio de Dirichlet . Recuperado: 30 de marzo de 2020. (indefinido)

diccionarios y enciclopedias	gran chino Britannica (en línea)