Skip to content

Solución: por tres o más cinco

by en 06/04/2014

¡Hola!

Como cada domingo, ha llegado el momento de dar la solución a nuestro acertijo de la semana. En él, os hablábamos de una forma de generar números consistente en empezar con el número 1 y, en cada paso, o bien multiplicar 3, o bien sumar 5 al valor obtenido hasta ese momento. No todos los números pueden generarse de esta forma, por lo que las preguntas que os hicimos consistían en varios números y teníais que decirnos si podían o no escribirse como una serie de multiplicaciones por 3 y sumas de 5.

El acertijo fue puesto como un problema de los concursos regionales de ProgramaMe celebrados de Madrid y Reus hace varias semanas. En ese caso, se esperaba que los participantes hicieran soluciones “de programador”. En concreto, la solución directa del problema es recursiva:

  • Casos base:
    • Si el número a comprobar es 1 o 3, entonces contestar que sí.
    • Si no, si el número es menor que 6, contestar que no.
  • Casos recursivos:
    • Si el número es divisible por 3 y el resultado de la división por 3 se puede escribir como secuencia de multiplicaciones de 3 y sumas de 5, contestar que sí.
    • En otro caso, responder si el número menos 5 se puede escribir como secuencia de multiplicaciones de 3 y sumas de 5.

Aunque es válida, esta solución es muy lenta en los casos “no” debido a la repetición de las comprobaciones. Por tanto, era necesario usar una tabla para recordar los resultados de los números y no repetir cálculos.

Pero, como decimos, esta es la solución “de programador”. El día del concurso os aseguramos que había una manera “matemática” de resolver el problema, lo que lo convierte en un acertijo estupendo al hacer viable dar las respuestas sin utilizar un ordenador 🙂 Ha llegado el día de contárosla.

En el planteamiento del problema os poníamos dos ejemplos:

23 = ((1 + 5) × 3) + 5
77 = (((1 × 3 + 5) × 3) × 3) + 5

En ambos casos, la cadena de multiplicaciones por 3 y sumas de 5 es mínima, pues se ha sumado 5 lo antes posible para que les afecten las multiplicaciones por 3. Sin embargo, ambas expresiones pueden expandirse para quitar los paréntesis. Tendremos:

23 = 1 × 3 + 5 + 5 + 5 + 5 = 3¹ + 4 × 5
77 = 1 × 3 × 3 × 3 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 = 3³ + 10 × 5

Fijaos que en ambos casos lo que tenemos es una potencia de 3 sumada a un múltiplo de 5. Cualquier secuencia de multiplicaciones por 3 y sumas de 5 que construyamos para representar números, podrá ser reescrita de este modo si le dedicamos el tiempo suficiente a quitar los paréntesis. De hecho, las expresiones finales (como 3¹ + 4 × 5) son también secuencias de multiplicaciones por 3 y sumas de 5, con la particularidad de que se han hecho primero todas las multiplicaciones, y luego todas las sumas.

Una vez que nos hemos dado cuenta de esto, saber si un número cualquiera se puede escribir con una secuencia es fácil. Basta restar al número las potencias de 3 menores que él, y mirar si el resultado es un múltiplo de 5. Si en algún caso lo es, contestaremos que sí. Si no, diremos que no.

Veamos las preguntas que os hacíamos:

  • 14 =
    • 30 + 13 ⇒ no
    • 31 + 11 ⇒ no
    • 32 + 5 ⇒ SI
  • 22 =
    • 30 + 21 ⇒ no
    • 31 + 19 ⇒ no
    • 32 + 13 ⇒ no
  • 86 =
    • 30 + 85 ⇒ SI (85=17 × 5)
  • 87 =
    • 30 + 86 ⇒ no
    • 31 + 84 ⇒ no
    • 32 + 78 ⇒ no
    • 33 + 60 ⇒ SI (60=12 × 5)
  • 89 =
    • 30 + 88 ⇒ no
    • 31 + 86 ⇒ no
    • 32 + 80 ⇒ SI (80=16 × 5)
  • 90 =
    • 30 + 89 ⇒ no
    • 31 + 87 ⇒ no
    • 32 + 93 ⇒ no
    • 33 + 63 ⇒ no
    • 34 + 9 ⇒ no

Como puede verse con, por ejemplo, el 89, es importante probar con todas las potencias de 3 anteriores, y no sólo con la más alta. Si con 89 probáramos únicamente con 34 (81) contestaríamos que no, algo incorrecto.

Este proceso es mucho más rápido que las pruebas recursivas que comentábamos al principio y es posible hacerlo a mano. Seguro que ahora eres capaz de afrontar los valores más altos que aparecieron en los comentarios, 6811 o 19763 🙂

Pero todavía hay una posibilidad más de mejora. Después de estas reflexiones, está claro que si el número n se puede escribir como secuencia de multiplicaciones por 3 y sumas de 5, también podrá escribirse así el número n + 5, el número n + 10 y, en general, n + 5×k (con k positivos). Es posible que algunos de esos números se puedan escribir de varias formas, por ejemplo:

253 = 31 + 50 × 5 = 35 + 2 × 5

pero no es importante. Lo que es importante es encontrar los números más bajos de cada una de esas “cadenas”, y saber cuantas hay. Esto permite una solución al acertijo todavía más impactante que puede programarse con una única expresión booleana (aunque con varios operadores lógicos encadenados). ¿Te atreves a buscarla? Si la encuentras, cuéntanosla en los comentarios 🙂 Y, como siempre, puedes probarla aquí.

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: