Peso en carga de $270$ kg

Question

Problema: Un total de $270$ kg de sandías, cada una de las cuales pesa como máximo $7$ kg, debe transportarse por $11$ portadores a la vez. Demuestre que si cada portador puede transportar hasta $30$ kg cada vez, esto puede hacerse independientemente del peso de las sandías individuales.

$\\$

Mi opinión sobre la solución: Sea el número de sandías $n$ . Sea el peso de las sandías $0< x_1 \leq x_2 \leq \dots \leq x_n \leq 7$ . Desde $$\sum_{k=1}^{n} x_k = 270 $$ y $7n \geq n\cdot x_n \geq 270$ encontramos $n \geq 39$ .

Para $39 \leq n \leq 44$ , $\{ x_1, x_2, x_3, x_4\}, \{ x_5, x_6, x_7, x_8\}, \dots, \{ x_{41}, x_{42}, x_{43}, x_{44}\}$ grupos pueden ser transportados por $11$ portadores.

Para $n>44$ No tengo ni idea. Para un tamaño suficientemente grande $n$ algunos pesos de las sandías disminuirán. Gracias por su interés...

Answer 1

Supongamos que distribuimos los melones de la siguiente manera. Ordenarlos por peso decreciente (empezando por el más pesado), y dar siempre el siguiente melón a algún portador que tenga suficiente capacidad de carga no utilizada. Afirmo que este algoritmo siempre consigue distribuir toda la carga entre los once porteadores.

Supongamos por el contrario que no asignamos el número de melón $n$ pesando $x$ kilos a algún transportista. Para que esto ocurra debemos haber asignado ya a cada transportista una carga de más de $30-x$ kilos. Si $w$ representa el peso combinado de los melones ya asignados, llegamos a la desigualdad $w>11(30-x)=330-11x$ . Por otra parte, porque al menos $x$ kilos restantes, hemos asignado como máximo $270-x$ kilos, y por lo tanto $w\le 270-x$ (con igualdad sólo si se trata del último melón). Uniendo estas piezas obtenemos $$ 330-11x< w\le 270-x, $$ a partir de la cual (ignorando la variable ficticia temporal $w$ ) resuelve inmediatamente $x>6$ . Recordando que el $n-1$ todos los melones pesan $\ge x$ kilos, tenemos al menos $n$ melones de más de $6$ kilos cada uno. Porque $nx\le 270$ se deduce que $n\le 44$ . Pero el argumento de la OP muestra que la distribución de como máximo $44$ melones, cada uno de los cuales pesa como máximo $7$ kilos, no plantea problemas en general, y para nuestro algoritmo en particular. Por lo tanto, no puede plantearse la situación problemática.

---

Cabe señalar que $270$ kilos es la carga total máxima que se garantiza que el grupo de transportistas puede transportar. Inspirándonos en el argumento vemos que si una carga total de $270+\epsilon$ kilos se compone de $45$ melones, cada uno de los cuales pesa $6+\epsilon/45$ kilos, entonces la tarea se hace imposible. Para $45>4\cdot11$ por lo que, según el principio del encasillamiento, al menos un transportista debe transportar al menos $5$ melones, haciendo que su carga se $30+\epsilon/9$ kilos, que es demasiado.