Una mudanza con 54 cajas

Por Clara Grima, el 14 mayo, 2014. Categoría(s): Mateaventuras ✎ 29

–Madre mía, ¡qué lío tenemos aquí, Mati! No vamos a terminar de ordenar esto nunca –exclamó Ven mirando a su alrededor.

–Tranquilo, Ven –lo tranquilizó ella –. Despacito y buena letra…

–Que el hacer las cosas bien importa más que el hacerlas, ¿no? –remató Sal la frase de la pelirroja –Esa cita es de Antonio Machado, ¿verdad, Mati?

–Ajá –dijo Mati mientras abría no sin esfuerzo otra caja en la otra punta del salón.

–Tú, poeta –interrumpió Ven dirigiéndose a su hermano –, dime dónde guardamos los patines. Y quítate esas gafas, que pareces un niño loco.

Mati_Naukas2_1

 

 

–Voy, Ven –respondió el gafotas –. En realidad no queda tanto,  son solo 54 cajas, exagerao.

–¿Te parecen pocas cajas, gafotas? –protestó el pequeño –El señor del camión nos ha mirado con desconfianza, seguro que él hubiera conseguido guardarlo todo en menos cajas…

–Bueno, bueno, Ven –dijo de pronto Mati –, el problema de almacenar objetos es en el menor número de cajas posible no es fácil ni siquiera para el señor de la casa de mudanza. De hecho, es un problema de los que los matemáticos llamamos de naturaleza NP-duro.

–Ah, ya me acuerdo, Mati –interrumpió de nuevo Ven (al que ahora llaman a menudo ‘Pelanas’ en casa desde que se ha dejado crecer la melena) –, esos son de los que no se pueden resolver ni con ordenador, ¿no?

–Eso es, Ven –asintió la gafotas –. De los que no se puede saber su solución óptima, la mejor, ni con la computadora más potente. A este problema, el de empaquetar en el menor número de cajas se le conoce, como el problema del bin packing, en inglés, que significa precisamente eso, empaquetamiento (packing) en caja (bin).

–¿Por qué es tan difícil, Mati? –preguntó Sal con su curiosidad habitual.

–Pues… A ver… Entre otras cosas –dijo esta –porque el número de combinaciones de objetos que se pueden hacer para empaquetar es muy, muy grande, enorme y habría que comprobarlos todos.

–Entonces, ¿no hay ningún método para hacerlo lo mejor posible? –volvió a preguntar Sal.

–Bueno, hay distintos métodos que dan soluciones relativamente buenas –contestó ella –, pero no hay ninguno que se pueda hacer en tiempo razonable para encontrar la mejor.

–¿Nos cuentas alguno, Mati? –le pidió.

–Vale –les dijo –, así descansamos un poco de la mudanza.

Los niños se sentaron a escuchar a Mati. Gauss también, le gusta hacerse el interesante. Mati empezó a contarles:

Mati_Naukas2_2

 

–El problema del empaquetamiento en cajas para una mudanza en realidad es un problema tridimensional, porque estamos tratando de resolver un problema de volúmenes. Si fuera un problema de áreas, por ejemplo de colocar pegatinas de distintas formas (sin superponerlas) en el menor número de cartulinas posibles, sería un problema bidimensional, de 2 dimensiones. Pero os voy a contar la versión unidimensional, solo una dimensión, porque es más fácil para nosotros y nos sirve para hacernos una idea tanto de la versión de 2 dimensiones como de la de 3 dimensiones del problema.

Así que vamos a pensar en una de las dimensiones, por ejemplo, la altura. Nuestros objetos (los que tenemos que empaquetar) serán todos rectángulos con la misma base y lo que varía de unos a otros es la altura. Las cajas donde queremos agruparlos serán también rectangulares, con la misma base que los objetos y con altura, por ejemplo, de altura 10. Vamos a pensar que nos van dando objetos de distintas alturas en este orden: {4, 8, 5, 1, 7, 6, 1, 4, 2, 2} y que queremos colocarlos en cajas de altura 10, usando el menor número posible de cajas.

Mati_54_1

–Por lo menos necesitamos 4 cajas, Mati –exclamó Ven –, porque si sumas todas las alturas nos da 40.

–Eso es, Pelanas –dijo Mati sonriendo –, vamos a ver si lo conseguimos. El primer método que os voy a enseñar es el Next Fit: si no cabe en esta, en la siguiente. No es un método demasiado eficiente pero es muy simple. Empezamos con una caja y vamos metiendo los objetos siguiendo el orden de izquierda a derecha, si al tomar un nuevo objeto no nos cabe en esa caja, la soltamos y cogemos una caja nueva. Y así sucesivamente.

–O sea –dijo Ven –, cogemos la primera caja y metemos el objeto de 4, que es el primero por la izquierda, ¿no?

–Eso es –confirmó Mati.

Mati_54_2

–Y ahora, como el siguiente no cabe porque mide 8, tenemos que coger otra caja.

–Sí, señor, así es, Pelanas –respondió Mati con un guiño.

Mati_54_3

–El siguiente que es de 5 no cabe en esta segunda caja –siguió Ven –, así que cogemos otra nueva, ¿no?

–Ajá.

Mati_54_4

–¿Y por qué no lo metemos en la primera, Mati? –quiso saber Sal.

–Porque no es ese el método que estamos usando –dijo ella –. Con nuestro método no tenemos que recordar como están las cajas anteriores, ni volverlas a mirar: si no cabe en la que estoy usando en ese momento, tomo una nueva.

–Pues nada, cogemos otra caja –siguió el pequeño.

Sal y Ven siguieron colocando las cajas, en el dibujo que Mati les había hecho en un papel, siguiendo el método del Next Fit hasta que las colocaron todas.

Mati_54_5

–Necesitamos 6 cajas –concluyó Sal –. Demasiadas, creo yo.

–Sí, son muchas –dijo Mati –, pero, como os he dicho antes, este método tiene la ventaja de que no tenemos que estar pendientes de cómo de llenas están las cajas que ya hemos usado. Es un método que no necesita usar mucha memoria. En cualquier caso, os voy a proponer otro método, a ver si lo hacemos con menos cajas. Se trata del First Fit: en la primera caja que quepa. Hacemos como antes, los vamos colocando tal como aparecen de izquierda a derecha, pero miramos de las cajas que vamos usando, cuál es la primera en la que cabe.

–Empezamos igual que antes, ¿verdad? –preguntó Ven.

–Sí, claro.

Mati_54_2

–Y seguimos igual que antes, ahora el 8 va a otra caja –dijo Sal.

–Eso es –confirmó Mati.

Mati_54_3

–Pero ahora la del 5, la metemos en la primera caja, ¿verdad, Mati? –dijo Ven con entusiasmo.

–Efectivamente, caballero.

Mati_54_6

–Y la siguiente del 1 también la podemos poner en la primera caja, Ven –dijo Sal.

Mati_54_7

Los dos hermanos siguieron organizando las cajas con el First Fit hasta que las colocaron todas.

Mati_54_8

 

–Huy, qué rabia –dijo el pelanas –, hemos tenido que usar la quinta caja para meter un objeto de 2, y teníamos 2 huecos de 1… ¿Lo podemos partir por la mitad, Mati?

–¿Sí? –respondió ella – ¿Y si ese objeto de 2 es tu álbum de cromos del mundial?

–Vale, vale, lo pillo –aceptó el pequeño.

–¿Queréis que intentemos mejorarlo un poco? –propuso la pelirroja a los niños.

–¡Sí! –dijeron ellos al unísono.

–Una mejora de estos métodos –siguió Mati –se puede conseguir si sabemos desde el principio, como en nuestro ejemplo, cuántos objetos hay que colocar y de qué tamaño. Pero eso no suele pasar en la vida real…

–¿Por qué? –la interrumpió el gafotas.

–Porque, como habéis comprobado con nuestra mudanza –dijo ella –, cuando crees que has empaquetado todo, aparece un nuevo objeto que hay que guardar.

–Toma, claro.

–El método que os propongo consiste en, conocidos todos los objetos que tenemos que guardar, ordenarlos por tamaño antes de empezar.

–¿De mayor a menor? –preguntó Ven.

–Sí, eso es de mayor a menor, Ven.

Los niños dibujaron de nuevo los objetos, pero ahora ordenados de mayor a menor.

Mati_54_9

–¿Y ahora qué hacemos, Mati? –preguntó Sal –¿El First Fit o el Next Fit?

–El que vosotros queráis.

–Hacemos el First, ¿vale, Ven?

–Pues, vale.

–Ponemos el 8 en la primera caja…

–El 7 en la segunda, el 6 en la tercera y el 5 en la cuarta –apostilló Ven –. Todos esos números por parejas suman más de 10 y no caben en ninguna caja dos de ellos.

–Muy bien, Ven –dijo Mati –. Efectivamente, con los 4 primeros usamos ya 4 cajas.

Mati_54_12

–Sí, Ven –dijo su hermano –, pero ahora, si seguimos el orden y vamos colocando en el primer hueco que vamos encontrando, fíjate qué nos queda:

Mati_54_13

–¡Toma, toma, toma! ¡Cómo mola! –gritó Ven –¡4 cajas! ¡No se puede hacer mejor! ¡Eres un crack, Sal! ¡Elegiste bien el First!

–No dudo que Sal sea un crack –dijo Mati –, pero en este ejemplo, si lo hacéis con el Next Fit, también salen 4.

–Vamos a hacerlo –propuso Ven con entusiasmo.

–Yo creo que eso se lo dejamos a nuestros amigos para que lo intenten, ¿vale? –dijo la gafotas –Nosotros tenemos que seguir con la mudanza, que no terminamos.

–Pues tampoco es tan difícil, Mati –dijo Sal.

–Bueno, es que hemos hecho unos ejemplos con la versión más simple –respondió ella –. Pero, ¿y si no todos los objetos tienen la misma forma? ¿Y si podemos escoger cajas de distintos tamaños? ¿Y si son objetos tridimensionales? ¿Y si hay que guardar patines, drones de juguete, balones… ?

–Vale, vale –aceptó Sal arrugando la nariz –, puede ser muy, muy difícil, sí. Voy a seguir colocando cosas.

–Sí, a ver si terminamos hoy… –añadió Ven –. Y luego llamamos a Culogoma para decirle que ya estamos en Naukas, ¿vale?

–Claro –respondió Mati –, pero yo creo que ya debe saberlo porque nuestro Gauss lleva un rato ahí con su móvil…

Mati_Naukas_2_3

FIN

Hoy es un día muy especial para los protagonistas de estas historias, porque hoy hace 3 años que aparecieron por primera vez. Lo hicieron en el Pequeño Libro de Notas, un maravillosos semanario infantil que, por cosas de la vida,  dejó de publicarse en diciembre del año pasado

Desde aquel 14 de mayo les han pasado muchas cosas a Mati, Sal, Ven y Gauss, y todas buenas. Y desde entonces, cada año que han cumplido han recibido grandes regalos. Cuando cumplieron un año, dos nuevos amigos, Fis y Mr. Green, llegaron para contarnos muchas cosas interesantes de Física y Astronomía. Con el segundo cumpleaños, nuestros amigos pudieron ver su libro Hasta el infinito y más allá en la calle.

En este tercer cumpleaños tienen también un regalo muy especial, la publicación de su primera mateaventura en Naukas. Nos han contado nuestros protagonistas que están un poco nerviosos porque no conocen a  los nuevos lectores. Bueno, Gauss  no, la verdad, es un perro muy valiente y temerario.

Muchas gracias a todos los que nos seguís desde hace 3 años o desde hace 3 días. Aunque haya quien diga que este mundo virtual es frío y deshumanizado, nos llega el cariño de muchos de vosotros. Muchas gracias, de todo corazón.

En este nuevo blog, y gracias a José Cuesta, podéis encontrar todos los capítulos anteriores de Mati y sus mateaventuras y también todos los de Mati, una profesora muy particular. Desde ahora, este será el rincón donde encontrar todo lo que tienen Mati, Sal, Ven y Gauss.

Nada más, esperamos que sigamos viéndonos por aquí a menudo.

Un beso muy gordo.

Clara y Raquel



29 Comentarios

    1. (Empezamos por problemas técnicos)
      A Mar y a mi (Nuria) nos ha parecido una buena manera de aprender matemáticas.
      El ingenioso «inventor» de esa forma de enseñar las matemáticas se ha basado en que la gente aprenda más fácil y sencillo cuando creen que es difícil.
      Nos alegramos de que haya personas buscando la manera de un mundo mejor y sin complicaciones.
      Es la primera vez que entramos en este proyecto y os felicitamos por esto.

  1. Los dibujos, y la exposición de las ideas son muy buenas. Gracias. Son una buena guía para los padres con chavales con curiosidad por la naturaleza y las mates.
    Creo, sinceramente, que arriesgáis mucho al tocar temas, que por su complejidad, son más aptas para cerebros adultos y con cierta experiencia; pero alguien tenía que intentarlo, sí señor; y creo que lo hacéis de la mejor forma posible.

    Un saludo.

  2. Es la primer vez que comento en todo lo que llevo leyendo Naukas (y ahora, sus blogs) para agradecer este (y los demás) post. Espero, sigan publicando para mostrar las matemáticas tal como acá se hace. Cada vez que leo algo acá, le tomo aún más amor del que ya le tengo.

    Hoy me voy súper contento con lo que acá he aprendido y que podré mostrar muy pronto en clase de Almacenamiento de Materiales (Prometo citar el post).

    Mil y mil gracias.

    Un abrazo.

  3. me ha encantado esta fascinante historia de los métodos para empaquetar las cajas.
    me encanta la forma en la que se cuenta y las ilustraciones.
    ¡¡¡GRACIAS CLARA Y RAQUEL!!!

  4. Esta bien explicado solo que hay algunas cosas que no entiendo,pero felicito a quien hizo esto porque tiene cosas que son faciles de entender, esta bien que hagan estas cosas asi los niños aprenden muchas mas cosas que son mas avanzadas.

  5. Buenos días, quería deciros que esta es una gran forma de introducir las matemáticas más complejas a los jóvenes, además los dibujos ayudan mucho a comprender el problema que estamos a tratar. Esta es una buena forma de comprender y de divertirse al mismo tiempo, aprender con los problemas que estamos a realizar y divertirse con los risueños dibujos.
    Un saludo desde el I.E.S. Rafael Dieste en la Coruña.

  6. A Mar y a mi (Nuria) nos ha parecido una buena manera de aprender matemáticas.
    El ingenioso inventor de esa forma de aprender las matemáticas se ha basado en que la gente aprenda más fácil y sencillo cuando la gente cree que es tan difícil.

  7. Me ha encantado esta forma de introducir las matemáticas en una historia como esta. Una historia de niños y adultos que me ha gustado. No visito mucho esta página pero las veces que la miro me quedo muy contento. Gracias Clara y Raquel por enseñar esta fascinante historia en esta asombrosa página.

  8. Me gusta mucho este artículo porque soluciona muy bien los problemas que suele tener la gente cuando se va de mudanza.
    Esta ingeniosa forma puede servirnos de mucho no solo en el empaquetar cosas sino en la vida ya que es una forma matemática sencilla que me encanta.

    Aunque es la primera vez que veo este artículo, enhorabuena por llevar tres largos años enseñándole a la gente cosas con tan buen nivel como esta.

  9. Es la primera vez que leo Mati y sus mateaventuras y me ha parecido muy interesante. Me parece que esta información podríqa servirle a muchas personas que se muden. Estoy esperando al siguiente reportaje, o mejor leer los anteriores. Quería también felicitarles por su llegada a Naukas.

  10. Me encanta la manera en la que acerca las matemáticas planteando la realidad como un problema matemático. Es la primera vez que os veo y me encanta. Enhorabuena seguid así.

  11. Es la primera vez que entro a esta pagina, me a gustado bastante les felicito por su reportaje de mati y sus mateaventuras , también me ha gustado porque lo han escrito de forma que nosotros podamos entenderlo.
    Me ha enseñado que las matemáticas son una buena herramienta para comprender la realidad.
    Felicidades, ya os seguiré mas veces.

  12. Naukas en si nos parece una buena web de investigacion.El articulo que mas me impresiono
    fue la de Mudanza Con 54 Cajas.A todos nos gusto mucho por su originaliedad.

  13. Me pareció muy bien la idea de poder crear de las matemáticas algo divertido y que se pueda entender fácilmente . También querría agradecer a Raquel García Ulldemolins por sus maravillosos dibujos que embellecen este post.

  14. Me gusto esta entrada . Este puzzle aunque ya sabia la respuesta desde el principio me gustó. Lo que mas me gustó eran los intentos fallidos y las explicaciones porque no funciona. Espero que haya otra entrada como esta.

  15. Muchas gracias por este post, doy gracias a la escritora, Clara y a Raquel, que me encantan sus dibujos. Este post me parece muy bueno me gusta mucho porque esto puede suceder en la vida real. La profe de mates tiene razón la matemática es la llave de la vida, se usa para todo.

  16. ¡Parece muy divertido! Me encantan tus dibujos, son preciosos. No sabía que existieran los métodos del First Fit y Next Fit, pero no entiendo lo de las dimensiones. Muy original el trabajo y nos vemos.

  17. No me encantan las matemáticas pero con estos dibujos y las aclaraciones del cómic me he parado a pensar.Sin duda os volveré a visitar. Buen trabajo y enhorabuena Clara y Raquel.

  18. Parece muy divertido , Es muy interesante. Las matemáticas me hacen entender muchas cosas de la vida. Doy la enhorabuena a Clara y Raquel. Un saludo, nos vemos.

  19. Esta pagina me ha gustado mucho y la volvere a visitar frecuentemente.
    Un saludo. Clara Grima y Raquel Garcia. Enhorabuena

  20. Este articulo me parece algo muy interesante porque habla de un tema bastante especial porque es original y que nunca se a visto

  21. Este experimento nos a parecido muy interesante a la vez que original ya que no lo habíamos visto en otros blogs de ciencia.Nosotros no somos experimentados en ciencias pero hemos llegado ha comprender algo del articulo.

Deja un comentario

Por Clara Grima, publicado el 14 mayo, 2014
Categoría(s): Mateaventuras