Prueba del Principio de Colocación Generalizado

Question

De mi libro Matemáticas Discretas de Rosen, no puedo entender la conclusión de la prueba.

EL PRINCIPIO DE ENCASILLAMIENTO GENERALIZADO: Si se colocan N objetos en k cajas, entonces hay al menos una caja que contiene al menos ⌈N/k⌉ objetos.

Prueba por contradicción:

Supongamos que ninguna de las cajas contiene más de ⌈N/k⌉ objetos. Entonces, el número total de objetos es como máximo ⌈N/k⌉-1 objetos.

$$⌈N/k⌉ < (N/k) + 1$$ $$k(⌈N/k⌉ - 1) < k[(⌈N/k⌉+1)-1] = N$$

Esto es una contradicción porque hay un total de N objetos.

No entiendo cómo esa desigualdad muestra que es una contradicción, ¿cómo han conseguido que la desigualdad muestre menos de N objetos?

Answer 1

La pretensión es que al menos uno de los $k$ cajas contienen al menos $\lceil N/k\rceil$ objetos.

La prueba pasa por la contradicción: Supongamos que la afirmación es falsa, entonces cada caja debe tener estrictamente menos de $\lceil N/k\rceil$ objetos, es decir, como máximo $\lceil N/k\rceil-1$ (el mayor número entero estrictamente menor que $n$ es $n-1$ )

Ahora bien, como hay $k$ cajas y cada caja tiene objetos $\leq\lceil N/k\rceil-1$ el número total de objetos de todas las cajas es $\leq k(\lceil N/k\rceil-1)\lt k\cdot N/k=N$ (utilizamos $\lceil x\rceil-1\lt x$ ) lo que nos da una contradicción ya que el número total de objetos de todas las cajas no puede ser estrictamente menor que $N$ (ya que $N$ es el número total de objetos de todas las cajas).

Fíjate en el único $\lt$ en la cadena de desigualdades en el penúltimo paso que hace que la desigualdad global sea estricta, es decir, nos da $N\lt N$

---

He aquí una forma informal (intuitiva) de interpretar el teorema:

Normalmente nos fijamos en el peor de los casos. Si queremos que el número de objetos en cada caja sea el menor posible a la hora de poner los objetos en las cajas, podemos hacerlo poniendo un objeto en cada caja y luego pasar a la siguiente caja y no llenar una caja anterior a menos que todas las cajas tengan el mismo número de objetos. Ponemos un objeto en la 1ª caja, luego uno en la 2ª,.. y así sucesivamente hasta la $k$ hasta que todas las cajas tengan un objeto y entonces repetimos lo anterior.

Si $N$ es un múltiplo de $k$ Entonces tendríamos $N/k$ objetos en cada caja al final.

De lo contrario, tendremos la primera $x$ cajas con $\lceil N/k\rceil$ objetos en los que $x$ es el resto cuando $N$ se divide por $k$ y el resto de las cajas tendrán exactamente un objeto menos que la primera $x$ cajas.

Answer 2

La confusión parece estar en la frase "el número total de objetos es como máximo..." Eso está mal dicho, porque es claramente falso: el número total de objetos es exactamente $N$ . El número máximo de objetos en una sola caja es $⌈N/k⌉−1$ . Eso es porque estamos operando bajo la hipótesis de que ninguna de las cajas contiene al menos $⌈N/k⌉$ objetos (otro error en la grabación de la prueba). Fíjate en que se trata de una prueba por contradicción, lo que significa que estamos tratando de asumir lo contrario de lo que estamos tratando de probar, y derivar una contradicción. Intentamos demostrar que alguna caja tiene al menos $⌈N/k⌉$ objetos lo contrario de lo que no es ninguna caja tiene más de $⌈N/k⌉$ objetos pero en cambio ninguna caja tiene al menos $⌈N/k⌉$ objetos .

Answer 3

Mi primera pregunta es cómo han decidido que el número total de objetos es como máximo $⌈N/k⌉-1$ . ¿De dónde sacaron el $-1$ ?

Por si acaso, cada caja tiene menos de $⌈N/k⌉$ elementos, es decir, como máximo $⌈N/k⌉-1$ (esto es probablemente lo que querían decir con "el número total de objetos es como máximo $⌈N/k⌉-1$ objetos" ). En total para todo objetos en todo de $k$ cajas (que sabemos que es $N$ ) será como máximo $k(⌈N/k⌉-1)$ objetos, o en otras palabras $N \leq k(⌈N/k⌉-1)$ .

No entiendo cómo a partir de la desigualdad que obtuvieron es una contradicción porque hay un total de $N$ ¿Objetos?

Parece que te has equivocado de paréntesis. Tenemos $⌈N/k⌉ < (N/k) + 1$ (por la definición de la función techo), por lo que $$N \leq k(\color{red}{⌈N/k⌉} - 1) < k(\color{red}{((N/k)+1)}-1) = k(N/k) = N.$$

Y así se consigue $N<N$ , una contradicción...

Answer 4

Así que tienes $k$ cajas y quiere demostrar que hay más de $r$ en una caja. Bueno, lo máximo que puedes tener en todas las cajas es $kr$ y si $kr\lt N$ no caben todos $N$ objetos en sin tener más de $r$ en una caja.

Así que ya tenemos la idea: ahora qué elegimos para $r$ ? Queremos el mayor número entero que podamos encontrar con $kr\lt N$ es decir, $r\lt \frac Nk$ . Ahora sabemos que $\lceil \frac Nk\rceil\lt \frac Nk+1$ , por lo que podemos elegir $r=\lceil \frac Nk\rceil-1$ para hacer el trabajo. Entonces sabemos que tenemos que tener más de $r$ es decir, al menos $r+1=\lceil \frac Nk\rceil$ en una de las cajas.

Así que he invertido la forma de pensar en ello. Pero para ir hacia adelante ahora, si queremos mostrar que hay al menos $\lceil \frac Nk\rceil$ en una de las cajas, que es nuestra $r+1$ y necesitamos $r=\lceil \frac Nk\rceil-1$ .

Entonces el máximo que podemos acomodar sin sobrepasar esto es $kr=k(r+1)-k \lt k(\lceil\frac Nk\rceil)-k\lt N+k-k=N$ .