Matemáticas | El principio del casillero

Supongamos que una bandada de 20 palomas vuela a un conjunto de 19 casilleros para posarse. Debido a que hay 20 palomas pero solo 19 casilleros, al menos uno de estos 19 casilleros debe tener al menos dos palomas. Para ver por qué esto es cierto, tenga en cuenta que si cada casillero tuviera como máximo una paloma, se podrían acomodar como máximo 19 palomas, una por casillero. Esto ilustra un principio general llamado el principio del casillero, que establece que si hay más palomas que casilleros, entonces debe haber al menos un casillero con al menos dos palomas en él.

 
Teorema –

I) Si “A” es el número medio de palomas por hoyo, donde A no es un número entero, entonces

• Al menos un casillero contiene ceil[A] (el menor entero mayor o igual que A) palomas
• Los casilleros restantes contienen como máximo piso[A] (entero más grande menor o igual que A) palomas

O

II) Podemos decir que, si n + 1 objetos se colocan en n cajas, entonces al menos una caja contiene dos o más objetos.
La formulación abstracta del principio: Sean X e Y conjuntos finitos y sean una función.

• Si X tiene más elementos que Y, entonces f no es uno a uno.
• Si X e Y tienen el mismo número de elementos y f es sobre, entonces f es uno a uno.
• Si X e Y tienen el mismo número de elementos y f es uno a uno, entonces f es sobre.

El principio del casillero es una de las ideas más simples pero más útiles de las matemáticas. Veremos más aplicaciones que la demostración de este teorema.

• Ejemplo – 1: Si (Kn+1) las palomas se mantienen en n casilleros donde K es un número entero positivo, ¿cuál es el número promedio? de palomas por casillero?

  Solución: número promedio de palomas por hoyo = (Kn+1)/n
  = K + 1/n
  Por lo tanto, habrá al menos un casillero que contendrá al menos (K+1) palomas, es decir, ceil[K +1/n ] y el resto contendrá como máximo K, es decir, piso[k+1/n] palomas.
  es decir, el número mínimo de palomas necesario para garantizar que al menos un casillero contenga (K+1) palomas es (Kn+1).

• Ejemplo – 2: Una bolsa contiene 10 canicas rojas, 10 canicas blancas y 10 canicas azules. ¿Cuál es el número mínimo? ¿Cuántas canicas tienes que elegir al azar de la bolsa para asegurarte de obtener 4 canicas del mismo color?

  Solución: Aplicar el principio del casillero.
  No. de colores (casilleros) n = 3
  No. de canicas (palomas) K+1 = 4
  Por lo tanto el mínimo no. de canicas requeridas = Kn+1
  Al simplificar obtenemos Kn+1 = 10.
  Verificación: ceil[Promedio] es [Kn+1/n] = 4
  [Kn+1/3] = 4
  Kn+1 = 10
  es decir, 3 rojo + 3 blanco + 3 azul + 1 (rojo o blanco o azul) = 10

Forma fuerte del principio del casillero:

Teorema: Sea q ₁ , q ₂ , . . . , q _n sean enteros positivos.
Si q ₁ + q ₂ + . . . + q _n – n + 1 objetos se colocan en n cajas, entonces la primera caja contiene al menos q ₁ objetos, o la segunda caja contiene al menos q ₂ objetos, . . ., la n-ésima caja contiene al menos q _n objetos.
 
La aplicación de este teorema es más importante, así que veamos cómo aplicamos este teorema en la resolución de problemas.

• Ejemplo: 1: en un departamento de informática, se puede formar un club de estudiantes con 10 miembros del primer año u 8 miembros del segundo año o 6 del tercer año o 4 del último año. ¿Cuál es el número mínimo? de estudiantes que tenemos que elegir al azar del departamento para asegurarnos de que se forme un club de estudiantes?

  Solución: podemos aplicar directamente de la fórmula anterior donde,
  q ₁ = 10, q ₂ = 8, q ₃ = 6, q ₄ = 4 y n = 4
  Por lo tanto, el número mínimo de estudiantes requerido para asegurar que se forme un club departamental es
  10 + 8 + 6 + 4 – 4 + 1 = 25

• Ejemplo – 2: Una caja contiene 6 bolas rojas, 8 verdes, 10 azules, 12 amarillas y 15 blancas. ¿Cuál es el número mínimo? ¿Cuántas bolas tenemos que elegir al azar de la caja para asegurarnos de obtener 9 bolas del mismo color?

  Solución: Aquí en esto no podemos aplicar ciegamente el principio de la paloma. Primero veremos qué sucede si aplicamos la fórmula anterior directamente.
  De la fórmula anterior tenemos la respuesta 47 porque 6 + 8 + 10 + 12 + 15- 5 + 1 = 47
  Pero no es correcta. Para obtener la respuesta correcta, debemos incluir solo bolas azules, amarillas y blancas porque las bolas rojas y verdes son menos de 9. Pero estamos eligiendo al azar, por lo que incluimos después de aplicar el principio de paloma.
  es decir, 9 azules + 9 amarillas + 9 blancas – 3 + 1 = 25
  Dado que estamos eligiendo al azar, podemos obtener todas las bolas rojas y verdes antes que las 25 bolas anteriores. Por lo tanto, sumamos 6 rojas + 8 verdes + 25 = 39.
  Podemos concluir que para sacar 9 bolas del mismo color al azar, hay que sacar 39 bolas de una caja.

 
Referencias:
http://www2.fiit.stuba.sk/~kvasnicka/Mathematics%20for%20Informatics/Rosen_Discrete_Mathematics_and_Its_Applications_7th_Edition.pdf
 
Este artículo es una contribución de Saikiran Goud Burra . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.