Skip to content

Solución: los juguetes de Jaime

by en 21/04/2013

Hola!

Se acaba la semana, lo que significa que toca resolver el acertijo que os proponíamos el lunes. Se trataba de decidir el tamaño mínimo necesario para un grupo de cajas de modo que fueran suficientes para guardar los juguetes de Jaime siguiendo la peculiar forma de guardarlos del niño. Os poníamos el ejemplo de una lista de juguetes de tamaños 1, 2, 3, 4 y 5, que queremos guardar en 3 cajas. Los juguetes se meten en las cajas en orden, tanto de juguetes como de cajas. El tamaño mínimo de las cajas resultaba ser 6, para meter los juguetes de la forma [1, 2, 3], [4], [5], donde cada bloque entre corchetes representa una caja.

Os proponíamos como primera pregunta el tamaño mínimo de tres cajas para guardar los juguetes de tamaños 1, 2, 3, 4 y 8. En los comentarios, Borja dijo que el tamaño era de 8. ¡¡Y acertó!! Efectívamente, la colocación de los juguetes con cajas de tamaño 8 será [1, 2, 3], [4], [8]. Un tamaño menor no tiene sentido, porque los juguetes no pueden partirse y no podremos meter el último juguete, de tamaño 8, en una caja de tamaño menor que 8.

El segundo caso era más difícil, por ser más largo. El número de cajas deseado era 4, y los tamaños de los juguetes 5, 8, 1, 3, 7, 3, 9, 3, 2 y 6. Borja dijo que la respuesta era 12. Pero en este caso se equivocó 😦 Con ese tamaño, la asignación de cajas queda:

[5],  [8, 1, 3], [7, 3], [9, 3], [2, 6]

lo que significa que necesitamos cinco cajas, y no cuatro como nos pedían.

El problema, como le hizo ver David en los comentarios, estaba en el razonamiento. No podemos asegurar que el “tamaño medio de la caja” nos sirva para dar la respuesta, porque no podemos partir los juguetes. David sugería una forma de resolverlo diferente, por  tanteo, pero no puso a qué solución llegaba 🙂

Si el acertijo se resuelve con lápiz y papel, hacerlo por tanteo supone intentar ajustar una solución que ya tenemos. Por ejemplo, partiendo de la propuesta de tamaño 12 que nos dijo Borja y viendo cómo quedan las cajas, vemos que tenemos una caja de más, y que la primera está demasiado vacía (tiene un único juguete de tamaño 5). Haciéndola un poco más grande (de 13), podríamos meter el siguiente juguete (de tamaño 8) y quizá así nos ahorremos la quinta caja. Y de hecho, es así. Con tamaño 13 la asignación queda:

[5, 8], [1, 3, 7], [3, 9, 3], [2, 6]

¡Esa era la solución correcta de la segunda pregunta! El tamaño mínimo es 13.

Pero ya sabéis que nosotros con esto no nos conformamos… ¿cómo lo hemos hecho realmente? ¿Seríamos capaces de resolverlo si el número de juguetes fuera 200, y tuviéramos que decidir el tamaño mínimo para 40 cajas? Seguramente nos resultaría bastante complicado usar el sentido común para ponernos a ajustar los tamaños, porque sería más difícil tener una visión global de lo que está ocurriendo, y de cuánto subir el tamaño para ahorrarnos cajas. Y, lo que es peor, aunque en este ejemplo no ha ocurrido, podríamos vernos obligados a reducir el tamaño por si nos hemos pasado y hay un tamaño menor que también nos sirva. Y saber cuánto reducir el tamaño es todavía más difícil que saber cuánto ampliarlo. En resumen, para preguntas más complicadas de las que os proponíamos, necesitamos una forma sistemática de resolver el acertijo. Además, sólo si se consigue un modo estructurado de resolver el acertijo (y no uno basado en la intuición) podréis, aquellos que queráis intentarlo, podremos programarlo en un ordenador.

Para sistematizar la resolución, tanto Borja como David dijeron cosas importantes. El tamaño mínimo de las cajas será el tamaño del juguete más grande. Como hemos dicho antes, no tiene sentido pensar que podremos usar cajas de un tamaño menor. Por ejemplo, si tenemos los juguetes de tamaños 10, 10, 10, 10 y decidimos comprar, vamos a ser brutos, 40 cajas, el tamaño mínimo de las cajas no podrá ser de menos de 10 (aunque de media pudieran ser de tamaño 1), dado que los juguetes no se parten. Con este caso, las cajas tendrían que ser de tamaño 10, y nos sobrarían 36 cajas que se quedarían vacías.

Por otro lado, también podemos poner un límite al tamaño máximo de las cajas. En el peor de los casos, podríamos vernos obligados a tener que meter todos los juguetes en una única caja (en realidad esto ocurre únicamente cuando hay sólo una caja, pero por poner un límite superior sencillo). Gracias a esto, tenemos acotada la solución: estará entre el tamaño del juguete más grande, y la suma de los tamaños de todos los juguetes. Ahora lo único que falta es saber, de todos esos números, cuál es el menor que nos sirve.

Para eso, hay que ser conscientes de que sabemos probar si un tamaño nos sirve o no. La forma de guardar los juguetes es sencilla; por tanto saber si podemos guardar los juguetes en 4 cajas de tamaño 12 es fácil: basta con ir metiendo juguetes en cajas y mirar si al final nos faltan cajas, o hemos tenido suficientes. En resumen, tenemos un valor mínimo para el tamaño de las cajas, un valor máximo, y sabemos probar si un valor es o no válido.

Ahora sólo queda… probar. Nos planteamos la hipótesis de que con el tamaño mínimo de caja es suficiente. Miramos si es cierto. Si lo es ¡ya tenemos la respuesta!. Si no, probamos con el tamaño de caja inmediatamente superior (sumando 1 al tamaño). Así, vamos probando y en cuanto nos encontremos el primer valor para el que los juguetes entran en las cajas disponibles, hemos encontrado la respuesta.

¡Esto es fácil y sistemático! Sin embargo, puede ser muy lento. En el caso de la pregunta, donde había 10 juguetes, el tamaño mínimo de las cajas era 9 (el juguete más grande) y el máximo era 47. Tendríamos que empezar a probar con 9, luego con 10, … hasta llegar a 13 que era la respuesta correcta. Si la pregunta hubiera sido para 2 cajas (y no para 4) habría sido mucho peor, porque habríamos tenido que subir hasta 24, que es la respuesta correcta para ese caso. ¡Eso son muchas pruebas! ¿Podemos hacerlo más deprisa, ahorrándonos trabajo?

La respuesta es que sí. ¿Alguna vez habéis jugado al “adivine mi número”? Una persona piensa un número entre 1 y 100 que otra tiene que averiguar recibiendo pistas de “mayor” o “menor”. Una forma inocente de jugar es probar todos de manera sistemática: ¿es el 1? ¿Es el 2? ¿Es el 3?

Pero ¡no es muy inteligente! Es mucho mejor empezar por la mitad. ¿Es el 50? Si nos dicen que el número buscado es mayor, entonces sabemos que la respuesta está entre 51 y 100, y pasamos a preguntar por el punto medio, el 75. Si nos dicen que es menor, entonces la respuesta está entre 1 y 49, y preguntaremos por el 25. De esa forma, vamos “encerrando” mucho más deprisa el número buscado, porque el rango de posibles valores lo reducimos a la mitad en cada pregunta. A esto los informáticos le llaman búsqueda binaria.

¡Eso es justo lo que podemos hacer aquí!. Volviendo al ejemplo de los 10 juguetes con sólo 2 cajas (no con 4), sabemos que el tamaño mínimo de la caja es 9 (el juguete más grande) y el máximo es 47 (la suma de todos). En lugar de probar con 9, luego con 10, luego con 11… probamos con el punto medio, el 28. Si lo hacéis veréis que con cajas de tamaño 28 tenemos suficiente y podemos guardar los 10 juguetes. Pero quizá no sea la respuesta correcta; puede haber un tamaño más pequeño que también nos sirva, por lo que hay que buscarlo. Es decir, la respuesta que estamos buscando (el tamaño mínimo) está entre 9 y 28 (incluído).

Ahora probamos el punto central de ese nuevo rango. ¿Puedo guardar los 10 juguetes con 2 cajas de tamaño 18? Resulta que no. Por tanto, sabemos que la solución está entre 19 y 28. Fijáos que ahora no incluímos el 18 en el rango, dado que la respuesta ha sido “no”. El 18 no es una respuesta válida, y lo excluímos.

Probamos con el número central, el 23 y vemos que tampoco se puede. Sabremos entonces que la respuesta está entre 24 y 28. En tres comprobaciones más llegaremos a la conclusión de que la respuesta es 24. En total, hemos tenido que probar con sólo 6 configuraciones, cuando en la forma inocente de probar con todas empezando en 9 habríamos tenido que probar con 16. ¡Esto es un ahorro enorme! La búsqueda binaria nos ha evitado un montón de trabajo 🙂

Como siempre, si queréis intentar programarlo, podéis probar vuestra solución aquí.

¡Hasta mañana!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: