¿Cuál es el principio del cajón?
Hay diez manzanas sobre la mesa. Necesitamos poner estas diez manzanas en nueve cajones. No importa cómo las coloquemos, encontraremos que habrá al menos un cajón con al menos dos manzanas. él. Este fenómeno es lo que llamamos el "principio del cajón". ?
El significado general del principio del cajón es: "Si cada cajón representa un conjunto, cada manzana puede representar un elemento. Si hay n + 1 elementos colocados en n conjuntos, debe haber Hay al menos al menos dos elementos en un conjunto."?
El principio del cajón a veces se denomina principio del casillero. Es un principio importante en combinatoria.
Principio del primer cajón:
Principio 1: Si se colocan más de n+1 objetos en n cajones, entonces al menos un cajón contiene no menos de dos piezas.
Prueba (por contradicción): si cada cajón solo puede colocar como máximo un objeto, entonces el número total de objetos es como máximo n×1, no n+k (k≥1) como se establece en el pregunta, por lo que no es posible.
¿Principio 2?: Coloque más de mn (m veces n) + 1 (n no es 0) objetos en n cajones, entonces al menos un cajón contiene no menos de (m +1) objetos.
Prueba (por contradicción): Si cada cajón puede poner como máximo m objetos, entonces n cajones pueden poner como máximo mn objetos, lo cual es inconsistente con la pregunta, por lo que es imposible.
¿Principio 3?: Pon infinitos objetos en n cajones, entonces al menos un cajón contiene infinitos objetos.
Los principios 1, 2 y 3 son expresiones del principio del primer cajón.
Principio del segundo cajón:
Coloque (mn-1) objetos en n cajones, uno de los cuales debe contener como máximo (m-1) objetos (por ejemplo, si coloca 3 ×5-1=14 objetos en 5 cajones, debe haber un cajón con un número de objetos menor o igual a 3-1=2).
Información ampliada:
Expresión general:
En la primera conclusión anterior, como en un año hay como máximo 366 días, al menos entre 367 personas Dos las personas nacieron el mismo día del mismo mes. Esto equivale a poner 367 artículos en 366 cajones, con al menos 2 artículos en el mismo cajón.
En la segunda conclusión, también puedes imaginar que 5 pares de guantes están numerados respectivamente, es decir, hay dos guantes cada uno con los números 1, 2,..., 5, y dos pares de el mismo número son un par. Toma 6 guantes cualesquiera. Tienen como máximo 5 números, por lo que al menos dos de ellos tienen el mismo número. Esto equivale a poner 6 artículos en 5 cajones, con al menos 2 artículos en el mismo cajón.
Una expresión más general del principio del cajón es:
“Si colocas arbitrariamente más de kn+1 cosas en n cajones vacíos (k es un entero positivo), entonces debe Hay al menos k+1 cosas guardadas en un cajón."
Utilizando el principio anterior, es fácil demostrar: "Entre 7 números enteros cualesquiera, la diferencia entre al menos 3 números es múltiplo de 3 "Porque cuando se divide cualquier número entero entre 3, sólo quedan tres restos posibles: 0, 1 y 2. Por tanto, al menos 3 de los 7 enteros tienen el mismo resto al dividirse entre 3, es decir, la diferencia entre dos. de ellos es múltiplo de 3.
Si hay un número infinito de objetos discutidos en el problema, hay otra expresión del principio del cajón:
"Pon un número infinito de cosas en n cajones vacíos arbitrariamente (n es un número natural), entonces debe haber un número infinito de cosas guardadas en un cajón."
La función gaussiana se utiliza para describir la forma general del principio del cajón: poner m elementos en n cajones, entonces Habrá al menos
[(m-1)/n]+1 elementos en uno de los cajones.
El contenido del principio del cajón es conciso, simple y fácil de aceptar. Desempeña un papel importante en los problemas matemáticos. Con él se pueden resolver muchas pruebas de existencia.
Este problema se puede demostrar simple y claramente de la siguiente manera:
Utilice seis puntos A, B, C, D, E y F en el avión para representar a cualquier persona que participe en el Asamblea 6 personas. Si las dos personas se conocían antes, conecte una línea roja entre los dos puntos que los representan; de lo contrario, conecte una línea azul; Considere las 5 líneas que conectan AB, AC,..., AF entre el punto A y los demás puntos. No tienen más de 2 colores.
Según el principio del cajón, se puede saber que al menos 3 de las líneas conectadas son del mismo color. También se puede suponer que AB, AC y AD son todas rojas.
Si una de las tres líneas que conectan BC, BD y CD (tal vez establecida en BC) también es roja, entonces el triángulo ABC es un triángulo rojo, y las tres personas representadas por A, B y C se conocían antes: si las tres líneas que las conectan BC, BD y CD son todas azules, entonces el triángulo BCD es un triángulo azul. Las tres personas representadas por B, C y D no se conocían antes.
No importa qué situación ocurra, es consistente con la conclusión del problema.
El problema del ensamblaje de seis personas es el caso especial más simple del famoso teorema de Ramsey en combinatoria. Las ideas de prueba de este simple problema se pueden utilizar para sacar otras conclusiones detalladas. Estas conclusiones constituyen un contenido importante de la matemática combinatoria: la teoría de Ramsey. De la prueba del problema del ensamblaje de seis personas, vemos una vez más la aplicación del principio del cajón.
Expresión:
Ampliándolo a situaciones generales tiene las siguientes expresiones.
Forma 1: Suponga que n+1 elementos se dividen en n conjuntos (A1, A2,..., An), y use a1, a2,..., an para representar los contenidos correspondientes de Estos n conjuntos son el número de elementos, entonces: existe al menos un determinado conjunto Ai, que contiene elementos con un valor ai mayor o igual a 2.
Demostración: (Prueba por contradicción) Supongamos que la conclusión no se cumple, es decir, para cada ai, ai<2, entonces como ai es un número entero, ai≤1, entonces existe:
a1 +a2+…+an≤1+1+…+1=n Entonces, existe al menos un ai≥2, es decir, debe haber un conjunto que contenga dos o más elementos. Forma 2: suponga que nm+1 elementos se dividen en n conjuntos (A1, A2,..., An), y use a1, a2,..., an para representar los elementos correspondientes contenidos en estos n conjuntos son números, entonces: existe al menos un cierto conjunto Ai, que contiene elementos cuyo valor ai es mayor o igual a m+1. Prueba: (Prueba por contradicción) Supongamos que la conclusión no se cumple, es decir, para cada ai, ai a1+a2+…+an≤m+m+…+m=nm Entonces, hay al menos un ai≥m+1 Expansión del conocimiento - Definición de la función gaussiana [x]: para cualquier número real x, [x] significa "no mayor que x El número entero más grande". Por ejemplo: [3.5]=3, [2.9]=2, [-2.5]=-3, [7]=7,... Generalmente, tenemos: [x]≤x<[x]+1 Forma 3: Suponga que n elementos se dividen en k conjuntos A1, A2,...,Ak Utilice a1, a2,...,ak para representar el número correspondiente de elementos en estos k conjuntos. Es necesario demostrar que existe al menos una cierta ai mayor o igual a [n/k]. Demostración: (Usa prueba por contradicción) Supongamos que la conclusión no se cumple, es decir, por cada ai existe ai<[n/k], por lo que existe: a1+a2+…+ak<[ n/k]+[n/k]+…+[n/k] =k?[n/k]≤k?(n/k)=n k piezas [n/k] ∴ a1+a2+…+ak Forma 4: Se dividen q1+q2+…+qn-n+1 elementos Para n conjuntos A1, A2,...,An, use a1, a2,...,an para representar el número de elementos correspondientes en estos n conjuntos. Es necesario demostrar que hay al menos algo de i. tal que ai es mayor o igual que qi. Prueba: (Usa prueba por contradicción) Supongamos que la conclusión no se cumple, es decir, para cada ai hay ai Entonces hay: a1+a2+…+an≤q1+q2+…+qn-n Entonces, la suposición no se cumple, por lo que debe haber una i, y el número de elementos en el i-ésimo conjunto ai≥qi Forma 5: Prueba: (Usar prueba por contradicción) poner infinito Los elementos se dividen en conjuntos finitos. Suponiendo que el número de elementos en este conjunto finito es finito, entonces la suma de números finitos debe ser un número finito. Esto entra en conflicto con la pregunta. no es cierto, por lo que debe haber un conjunto que contenga infinitos elementos. (El principio del casillero se puede extender a conjuntos infinitos a través de los infinitos números cardinales de Cantor). Materiales de referencia: Enciclopedia Baidu-Principio del cajón