Prueba del principio del casillero por contradicción

La prueba por contradicción implica asumir que un enunciado adecuado es verdadero y derivar una contradicción. De esto concluyes que la afirmación original es falsa.

Aquí, está tratando de probar que una caja debe contener al menos$\left \lceil \dfrac{n}{m} \right \rceil$elementos. Entonces, la ruta normal sería asumir que esto es falso y que ninguna de las cajas contiene tantos elementos.

Como sugerencia sobre cómo proceder, ¿cuál es el número máximo de elementos en cada caja si ninguno contiene al menos$\left \lceil \dfrac{n}{m} \right \rceil$? ¿Puedes relacionar eso con el hecho que se supone que debes usar?

Dejar$L$sea ​​el número total de elementos que puede colocar sin tener$\left \lceil \dfrac{n}{m} \right \rceil$o más en cualquiera de los$m$cajas

Asumir que$L\ge n$para que puedas encajar$n$elementos en las cajas.

El número máximo que puede colocar en cualquier casilla es

$\left \lceil \dfrac{n}{m} \right \rceil-1$.

El número máximo en$m$cajas es por lo tanto

$L=m\cdot\left \lceil \dfrac{n}{m} \right \rceil-m$.

Ahora usa la desigualdad que te dan para que$\left \lceil \dfrac{n}{m} \right \rceil\lt \dfrac nm+1$lo que da

$L\lt m\cdot\left (\dfrac nm+1\right)-m$que se reduce a$L\lt n$

Ahora supusimos al principio que$L\ge n$, entonces esto es una contradicción. Como no podemos tener$L\ge n$Debemos tener$L\lt n$.

Supongamos, con fines de contradicción, que podemos colocar el$n$artículos en las cajas de manera que el número máximo de artículos en cualquier caja sea$\left\lceil\frac nm \right\rceil-1 = \left\lceil\frac nm -1\right \rceil$.

Luego usando$n'$para contar el número total de elementos colocados en las cajas que vemos$n'\leq m\cdot\left\lceil\frac nm -1\right \rceil$y de la desigualdad dada tenemos$n'< m\cdot\left(\frac nm -1 +1\right) = m\cdot\frac nm =n$y$n'<n$es una contradicción, ya que asumimos todo$n$se colocaron los elementos.

Por lo tanto, el número de artículos en alguna caja debe ser mayor que la suposición, es decir$\left\lceil\frac nm \right\rceil$según sea necesario.