Skip to content

Solución: cuántos números reversibles

by en 21/04/2014

¡Hola!

Con el fin de las vacaciones de Semana Santa, llega el momento de resolver el acertijo que os proponíamos para estos días de descanso. En él, os hablábamos de los números reversibles, como aquellos que al ser sumados a sí mismos escritos de derecha a izquierda dan un resultado con todos los dígitos impares. Por ejemplo, el 36 al ser sumado al 63 (el 36 leído de derecha a izquierda) da 99, que tiene todos los dígitos impares. Para ser considerado reversible, un número y su inverso deben tener la misma cantidad de dígitos, de ahí que el 1010 no sea reversible, pues su versión leída de derecha a izquierda es el número 0101 que, al quitar el cero de la izquierda, tiene sólo tres dígitos. Como veremos ¡esto es muy importante para la solución!

Una vez definidos los números reversibles, os preguntábamos cuántos hay de 4 dígitos, y cuántos de 9. Como siempre, queríamos que lo contestarais sin necesidad de programarlo, es decir, sin probar uno por uno todos los posibles números, de ahí que pusiéramos una cantidad de dígitos bastante alta. En esta ocasión, sólo Gualterio se atrevió a darnos la solución y ¡acertó! Además, nos dio la solución a una pregunta que ni siquiera hacíamos, la cantidad de números reversibles de 10 dígitos. Veamos cómo llegar a ellas, empezando con la de 4 dígitos.

Como hemos dicho, no tiene sentido probar uno por uno todas las combinaciones. En lugar de eso, lo que vamos a hacer es pensar en la suma que estamos realizando, escribiendo el número reversible que estamos considerando como abcd, donde a es el primer dígito, b el segundo, c el segundo y, obviamente, d el cuarto y último. El número invertido será dcba, de modo que la suma que estamos haciendo es:

  abcd
+ dcba
——————

Fíjate que, debido a la propiedad conmutativa de la suma, mirando los dígitos individuales tenemos únicamente dos parejas de sumas: a+d y b+c. Para que el número abcd sea reversible, queremos que esas sumas den un resultado impar, y aquí juega una gran importancia el acarreo. Por ejemplo, si la suma de los dígitos de la derecha (d+a) da un resultado mayor que 9, entonces “nos llevaremos una” que irá a parar a la suma de los siguientes dígitos c+b. En lo sucesivo, en las sumas de dígitos pondremos siempre el dígito del primer sumando para saber a qué nos estamos refiriendo. Así d+a indica que estamos sumando el dígito d del número original (abcd) y el dígito a del invertido (dcba). Por tanto d+a es la suma de los dígitos menos significativos de los números, es decir los de la derecha del todo.

En este momento, no sabemos “cuánto nos llevamos” en la suma de cada dígito, y contestar esto esto será de vital importancia para resolver el acertijo. Vamos a ponernos otra vez la suma, escribiendo los acarreos en la parte superior, marcándolos, de momento, como desconocidos. Además, lo pondremos en formato tabla para poder poner más información que las simples letras que hemos puesto antes. En concreto, vamos a numerar las columnas de derecha a izquierda para podernos referir a ellas en la explicación:

4 3 2 1 0
? ? ? ?
a b c d
+ d c b a

Para resolver el acertijo, necesitamos ver qué posibilidades tenemos en los acarreos para garantizar que la suma de los dígitos será impar. Y es ahí donde tenemos que hacer uso de nuestra capacidad de análisis. Si intentasteis el acertijo y no se os ocurrió orientarlo de este modo, ¡esta es vuestra última oportunidad! ¡¡Dejad de leer y volved a intentarlo!!

¿Ya? ¿Lo habéis resuelto? 🙂 Pues venga, vamos a ver si coincidimos con la solución. ¡Estad atentos para no perderos!

Empezamos. Fijaos que no hemos puesto acarreo sobre los dígitos de la columna 0 (d+a), porque ellos nunca recibirán ninguno al no tener dígitos antes. Como todos los dígitos del resultado tienen que ser impares, obligatoriamente d+a debe dar un número impar. También debe ser impar ?+a+d (ponemos ? para indicar el, de momento, desconocido acarreo de esa columna). Para que ambas condiciones se cumplan, entonces irremediablemente el acarreo recibido por a+d debe ser 0, porque de otro modo o bien a+d o bien d+a serían pares. A si es que… ¡ya tenemos uno!:

4 3 2 1 0
? 0 ? ?
a b c d
+ d c b a

Con esto, sabemos que el acarreo recibido por a+d es 0. Ese acarreo llega de la suma de la columna 2, la anterior con ?+b+c, cuyo resultado debe ser, como siempre, impar. También debe ser impar la columna 1, ?+c+b. Por tanto, ambas interrogaciones deben ser iguales, de otro modo una columna daría un resultado par y la otra impar.

Cuidado, que vienen curvas. Sabemos que ?+b+c (columna 2) no genera acarreo sobre a+d (en la columna 3 hemos puesto ya el 0 encima). Eso significa que tampoco generará acarreo ?+c+b (columna 1), pues acabamos de llegar a la conclusión de que ambas interrogaciones tienen el mismo valor. Eso nos permite rellenar el acarreo de la columna 2 y, por ser las dos iguales, también la de la 1:

4 3 2 1 0
? 0 0 0
a b c d
+ d c b a

¡Ya casi está! Dado que d+a de la columna 0 no debe generar acarreo sobre la 1, entonces a+d de la columna 3 tampoco lo generará sobre la 4. Y con esto, completamos todo:

4 3 2 1 0
0 0 0 0
a b c d
+ d c b a

Llegados a este punto, podemos sacar algunas conclusiones:

  • De a y d sabemos:
    • a+d < 10 (no generan acarreo)
    • a y d son distintas de cero, pues de otro modo abcd o dcba tendrían un 0 a la izquierda y serían de tres dígitos en lugar de ser de cuatro como estamos buscando.
    • a+d debe ser impar
  • De b y c sabemos:
    • b+c < 10 (no generan acarreo)
    • b+c debe ser impar

Si te haces una tabla con las opciones, verás que de la pareja a y d nos salen 20 posibilidades, y de la pareja b y c nos salen 30. Combinadas, significa que tenemos 600 posibles configuraciones de los dígitos, que es justo la respuesta que estábamos buscando: hay 600 números reversibles de 4 dígitos tal y como nos dijo Gualterio 🙂 ¡Y lo hemos sacado sin necesidad de haber sumado nada!

Vamos con la otra pregunta, la cantidad de números reversibles de 9 dígitos. En este caso tenemos un número mucho más largo, abcdefghi. Como antes, nos pintamos la suma que vamos a hacer:

9 8 7 6 5 4 3 2 1 0
?0 0 ?1 ?2 ?3 ?4 ?3 ?2 ?1
a b c d e f g h i
+ i h g f e d c b a

En los acarreos hemos tomado algunos atajos gracias a la experiencia de la primera pregunta. En concreto, hemos puesto directamente el acarreo de a+i (columna 8) en 0, porque debe ser el mismo que el de la columna 0 (i+a) para que ambas sumas den un dígito impar. Además, ya sabemos que el acarreo recibido por cada pareja de sumas (por ejemplo b+h y h+b) debe también ser el mismo, por lo que hemos numerado las interrogaciones y hemos extendido el color de fondo para indicar la igualdad de las columnas. Cuando deduzcamos el valor de una de esas interrogaciones, automáticamente conoceremos el de la otra.

En esta ocasión, vamos a empezar por la columna del centro, la número 4 con la suma e+e. Estamos sumando dos veces el mismo dígito. Es fácil darse cuenta de que si se suma dos veces el mismo número, siempre se obtiene un número par (es como multiplicar por dos). Por tanto, como queremos que todos los dígitos del resultado sean impares, necesitamos acarreo sobre la columna 4:

9 8 7 6 5 4 3 2 1 0
?0 0 ?1 ?2 ?3 1 ?3 ?2 ?1
a b c d e f g h i
+ i h g f e d c b a

Ese acarreo nos llega de la columna anterior, la 3 con la suma de ?+f+d. Por tanto, ese mismo acarreo es generado por la columna 5 con la suma ?+d+f sobre la columna 6. Esto significa que ?2 es 1:

9 8 7 6 5 4 3 2 1 0
?0 0 ?1 1 ?3 1 ?3 1 ?1
a b c d e f g h i
+ i h g f e d c b a

Podemos hacer el mismo análisis con la columna 2. El acarreo que recibe, llega de la columna 1, ?+h+b. Por tanto ?+b+h, en la columna 7, generará también acarreo. Sin embargo esto rompe nuestra necesidad de que la columna 8 (a+i) no reciba acarreo, tal y como ya anotamos al principio. Esto sólo puede significar una cosa: no hay una configuración de acarreos que sea válida para conseguir que todos los dígitos de la suma sean impares. Por tanto, como también nos dijo Gualterio, no hay ningún número de 9 cifras que sea reversible. Curioso, ¿verdad?

Siguiendo razonamientos similares a los que hemos usado para resolver nuestras dos preguntas de la semana, seguro que eres capaz de obtener las restricciones de los acarreos de los números con una cantidad de dígitos diferentes, y luego sacar las combinaciones. Gualterio nos dio su respuesta para 10 dígitos: la nada despreciable cifra de 16.200.000 números reversibles.

Llega un momento en el que descubrirás un patrón (por ejemplo, no hay ningún número reversible de un sólo dígito, igual que hemos visto que no lo hay de 9). Una vez que obtengas el patrón, es fácil calcular la cantidad de números reversibles de cualquier longitud… En ese momento estarás ya preparado para programar tu solución y, como siempre, probarla aquí. ¡Esperamos que con esta ayuda los usuarios que han intentado el problema durante esta semana lo resuelvan correctamente!

Pero si no te atreves con tanto (o no eres de los que programa), al menos quizá quieras contestar la pregunta en el Proyecto Euler, que sirvió como inspiración para este acertijo y para el problema en Acepta el reto 🙂

¡Hasta el próximo!

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: