Skip to content

Solución: cuadros de chocolate

by en 12/05/2013

Hola!

Como todos domingos, toca dar la solución a nuestro acertijo de la semana. Os preguntábamos el mínimo número de cortes para conseguir tener separados en cuadrados una tableta de chocolate de NxM cuadrados iniciales. Os poníamos un par de ejemplos pequeños, de 2×2 y de 1×5. En el caso de 2×2 es 3. Como el tamaño es pequeño, es fácil ver mentalmente que sólo hay una forma de cortar la tableta: partirla por la mitad para conseguir dos porciones de 2×1 (o de 1×2), y luego partir cada una de ellas por la mitad otra vez, lo que suponen 3 cortes en total. Con la de 1×5 es aún más fácil: la única alternativa es ir separando cuadro por cuadro, donde el orden en el que se separen es indiferente.

Como siempre, os preguntábamos por tabletas un poco más grandes y más difíciles, de 3×2, 10×6 y 16×16. Dos lectores, Borja y Antonio, dieron dos soluciones diferentes. ¡Ninguno de ellos explicó por qué pensaban que eran correctas!

Para la tableta pequeña, de 3×2, es posible simular mentalmente las diferentes formas de hacer los cortes. Tenemos así principalmente dos opciones: la primera es cortarla de manera que se consigan dos porciones iguales de 3×1, y luego trocear cada una de ellas, lo que necesita dos cortes más. En total 5 cortes. La otra alternativa es empezar cortándola para conseguir una porción de 1×2 y otra de 2×2. Cortar la de 1×2 en cuadros necesita un corte más; cortar la de 2×2 necesita 3, como decíamos en nuestro ejemplo. Por tanto, también necesitamos 5 cortes.

Antonio, sin embargo, contestó que se necesitaban sólo 3 cortes. Suponemos que esa respuesta se explica pensando en cortar por la mitad y conseguir dos trozos de 3×1, y luego cortar, a la vez, cada uno de esos dos trozos para conseguir los cuadrados. Es decir, los dos cortes que se necesitan para partir cada uno de los trozos de 3×1 se harían a la vez, por lo que el total son 3 cortes. Quizá el enunciado no estaba del todo claro, pero asume que cada corte se hace sobre una única porción de chocolate, por lo que esa respuesta no es válida. De serlo, la forma más rápida de cortar una tableta de 2×2 sería de 2 cortes, y no de 3 como decíamos en el ejemplo.

Borja sí adivinó la respuesta para 3×2; pero, ¿y las otras dos? Mantener mentalmente todas las posibilidades para cortar una tableta de 10×6 o de 16×16 es bastante más difícil. Para contestar a esas preguntas es mejor pensar antes un poco en lugar de utilizar fuerza bruta simulando todas las opciones.

Si os fijáis, al principio, empezamos con una única porción de chocolate, que es la tableta entera. Cuando aplicamos el primer corte, conseguimos tener dos porciones, más pequeñas, de chocolate. En el siguiente corte, de nuevo, dividimos una porción en otras dos más pequeñas. Es decir, cada corte significa tener una porción de chocolate más de las que teníamos antes.

Para la pregunta del acertijo, los tamaños concretos de cada porción no importan; lo importante es cuántas hay. Al principio, empezamos con una única porción, y al final queremos tener NxM, el número total de cuadraditos de la tableta. Como cada vez que cortamos conseguimos una porción más, vamos a necesitar siempre NxM – 1 cortes, da igual cómo los hagamos. Por tanto, ¡¡Borja acertó!! Para trocear una tableta de 10×6 cuadros necesitamos 59 cortes, y para una de 16×16 se necesitan 255. ¡Enhorabuena, Borja, una vez más!

Queremos también felicitar a Antonio porque su respuesta, bajo la premisa de que en un corte pudiéramos partir varias porciones de chocolate a la vez, también sería correcta.

Una vez que se sabe el acertijo ¡programar esto es muy fácil! Este acertijo seguramente sea el más fácil de programar de todos los que os hemos puesto. De modo que si sabes C/C++ o Java, puedes probar tu 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: