Saltar al contenido

Solución: cuántos números reversibles

by

¡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!

¿Cuántos números reversibles?

by

¡Hola!

Como estamos de vacaciones, vamos con un acertijo un poquito diferente a los habituales, al menos en su forma de resolución. En el regional de ProgramaMe de Madrid y Reus del pasado Marzo, pusimos un problema sobre números reversibles que podéis resolver aquí. Existe una variante de ese problema mucho más emocionante, que nos sirve de acertijo para esta semana.

Empezamos con las definiciones. Se dice que un número es reversible si al ser sumado a él mismo leído de derecha a izquierda da un número con todos los dígitos impares. Por ejemplo, el número 36 es el número 63 cuando se lee en sentido inverso. 36+63=99 que tiene los dos dígitos impares, y por tanto 36 (y 63) son números reversibles.

Para que un número sea reversible debe cumplir una condición adicional: su versión leída de derecha a izquierda debe tener el mismo número de dígitos. Así, por ejemplo, el número 1010 no es reversible; su versión invertida es el 0101 y 1010+0101=1111 que tiene todos los dígitos impares. Sin embargo 1010 tiene cuatro dígitos, y 0101 tiene sólo tres, pues el cero de la izquierda es superfluo y no se cuenta.

Puedes comprobar que hay 20 números de 2 cifras que son reversibles. De 3 cifras hay 100. ¿Cuántos números reversibles hay de 4 cifras? Para evitar que resuelvas el acertijo probando uno a uno… ¿cuántos números reversibles hay de 9 cifras?

Como siempre, ¡cuéntanos tus conclusiones en los comentarios! Y, si sabes programar y quieres dedicarle un rato más, puedes probar tu solución aquí.

¡Hasta el domingo!

Solución: Hawking

by

¡Hola!

Esta semana os proponíamos un acertijo en el que había que colocar las letras en un “tablero” de modo que se minimizara el coste de referenciar las letras de una determinada frase sabiendo que el coste de cada referencia era la suma de la posición x y la posición y de cada letra dentro del tablero. Dicho así suena muy confuso, de modo que os poníamos el siguiente ejemplo. En el tablero:

1 2 3 4 5 6
1 A B C D 1 2
2 E F G H 3 4
3 I J K L M N
4 O P Q R S T
5 U V W X Y Z
6 5 6 7 8 9 0

la palabra “COSMOS” tiene un coste de:

(3 + 1) + (1 + 4) + (5 + 4) + (5 + 3) + (1 + 4) + (5 + 3) = 39

Os preguntábamos el menor coste posible para las frases “COSMOS”, “PROGRAMAME”, “ACEPTA EL RETO” y “MUCHO POR PROGRAMAR”, sabiendo que en cada frase recolocamos las letras a voluntad, y que un espacio no supone coste alguno.

Por desgracia, esta semana ¡nadie se ha animado con la solución! 😦 De primeras puede que impusiera… pero era cuestión de pensarlo un poco y resulta bastante sencillo. Para cada frase, si queremos minimizar el coste tenemos que conseguir que las letras más frecuentes cuesten lo menos posible. Como el coste de cada casilla es la suma de la x y de la y podemos saber los costes de cada celda antes de colocar las letras:

1 2 3 4 5 6
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 4 5 6 7 8 9
4 5 6 7 8 9 10
5 6 7 8 9 10 11
6 7 8 9 10 11 12

Ordenando los costes de las celdas y poniéndolos todos seguidos tenemos:

2 3 3 4 4 4 5 5 5 5 6

que salen de recorrer el tablero original por diagonales.

Ahora, para cada frase lo que queremos, como hemos dicho, es que las letras más frecuentes nos cuesten lo menos posible. Lo que tenemos que hacer es contar el número de apariciones de cada letra, ordenarlas por número de apariciones y darles a cada una el siguiente coste de la lista anterior.

Así, para “COSMOS”, la O y la S aparecen dos veces (da igual en qué orden las coloquemos), y la C y la M sólo una. Por tanto, los costes que queremos tener son:

Coste 2 3 3 4 4 4 5 5 5 5 6
Letra O S C M
Nº aparic. 2 2 1 1

Si multiplicáis el número de apariciones de cada letra por el coste (en la fila superior) obtendréis el resultado para “COSMOS”, que resulta ser 17.

Con “PROGRAMAME” la tabla queda:

Coste 2 3 3 4 4 4 5 5 5 5 6
Letra R A M P O G E
Nº aparic. 2 2 2 1 1 1 1

y el coste es 33.

Si hacéis lo mismo con “ACEPTA EL RETO” llegaréis al coste 40, y con “MUCHO POR PROGRAMAR” a 58.

Como siempre, si os animáis a programarlo y queréis probar vuestra solución, podéis hacerlo aquí.

¡Hasta el próximo!

Hawking

by

Stephen Hawking es uno de los científicos más destacados de nuestros días. Físico teórico, cosmólogo y divulgador, es conocido por libros como Historia del tiempo o, más recientemente, Breve historia del tiempo.

Aparte de por sus logros científicos, su imagen es reconocida en todos los rincones del planeta debido a su enfermedad motoneuronal relacionada con la esclerosis lateral amiotrófica, que lo tiene postrado en una silla de ruedas desde hace décadas.

Hoy se comunica a través de un sintentizador de voz; pero hace años usaba una cuadrícula con letras, a las que referenciaba una a una para construir palabras:

1 2 3 4 5 6
1 A B C D 1 2
2 E F G H 3 4
3 I J K L M N
4 O P Q R S T
5 U V W X Y Z
6 5 6 7 8 9 0

Por la forma de funcionar del dispositivo que usaba en aquél momento, referenciar cada letra le costaba cierto tiempo, proporcional a la suma de la fila y la columna de cada letra. Así, por ejemplo, la palabra “COSMOS” le suponía el siguiente esfuerzo:

(3 + 1) + (1 + 4) + (5 + 4) + (5 + 3) + (1 + 4) + (5 + 3) = 39

Si las letras hubieran estado colocadas de otra forma, decir esa misma palabra le habría costado un esfuerzo diferente.

Si podemos recolocar las letras en el tablero a voluntad, ¿cuál es el mínimo coste que podemos conseguir para decir precisamente la palabra “COSMOS”? ¿Y “PROGRAMAME”, “ACEPTA EL RETO” o “MUCHO POR PROGRAMAR”? En los dos últimos casos, asume que el espacio no supone esfuerzo.

Como siempre, si das con la solución, cuéntanosla en los comentarios 🙂 Y si te animas a programarla, puedes probarla aquí.

¡Hasta el domingo!

Solución: por tres o más cinco

by

¡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í.

Por tres o más 5

by

¡Hola!

Os pedimos disculpas por el retraso en la publicación del acertijo de la semana. Como algunos sabréis, hace dos semanas tuvo lugar el regional de Madrid y Reus de ProgramaMe, el concurso de programación para ciclos formativos; queríamos aprovechar uno de los problemas que se pusieron en él como acertijo de la semana, pero hemos sufrido problemas técnicos en Acepta el reto y no hemos podido tener los problemas disponibles hasta hoy.

Pero dejémonos de excusas y vamos a lo importante, que es para lo que estáis aquí: el acertijo 🙂 Cuenta la leyenda que un famoso matemático, tras aprender a sumar y multiplicar a la tierna edad de 3 años en apenas 5 días, se dio cuenta de que, empezando por 1, podía generar un montón de números sin más que multiplicar por 3 o sumar 5 a alguno de los que ya hubiera generado antes. Por ejemplo:

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

Sin embargo, por mucho que lo intentó, algunos números, como el 5, el 7 o el 15, le resultaron imposibles.

Con esta introducción, seguro que intuís las preguntas 🙂 ¿Es posible escribir, con una sucesión de multiplicaciones por 3 y/o sumas de 5, el número 14? ¿Y el 22? ¿Y el 86, el 87, 89 o 90?

En ProgramaMe la solución que se contó se centraba en que el ordenador probara posibilidades. Pero hay una forma de hacerlo mucho más rápida, que es perfectamente asequible para hacerla con lápiz y papel. Si das con ella, como siempre, puedes programarla y probarla aquí. ¡Anímate a ver si tu solución es más rápida que la de los concursantes! 🙂

Solución: el mayor máximo común divisor

by

¡Hola, un domingo más!

Es hora de resolver el acertijo de la semana. En él, os preguntábamos cuál era el mayor máximo común divisor que se podría obtener entre todas las parejas de números distintos que se pueden formar con los números entre 1 y 10, 1 y 100 y 1 y 99.999. Como ejemplo, os hacíamos la tabla del máximo común divisor de todas las parejas de números entre 1 y 5, y llegábamos a la conclusión de que el mayor era el 2.

Iván nos dio su respuesta y, aunque tuvo una buena intuición, no acertó del todo. Efectivamente, el número 2 es importante en la búsqueda de la solución, pero no en la manera en la que él lo usaba… ¡Veamos la respuesta correcta!

El máximo común divisor (MCD a partir de ahora) de dos números es el mayor número que divide, con resto 0, a otros dos. Queremos conseguir el mayor MCD posible de entre todas las parejas de números (distintos) en un rango. Supongamos que el MCD buscado se consigue con dos números que llamaremos a y b, y que no sabemos cuáles son. Lo que está claro, es que el MCD divide a ambos, y por tanto:

a / MCD = p
b / MCD = q

Queremos que el MCD sea lo más alto posible, por lo que el resultado de la división debe ser lo más pequeño posible. Como los dos números de la pareja (nuestros a y b) no pueden ser iguales, entonces p y q tampoco pueden serlo. Y como deben ser lo más pequeños posible, sólo tenemos una opción, que los resultados de la división sean 1 y 2:

a / MCD = 1
b / MCD = 2

Fíjate que si p (o q) fuera 3, entonces irremediablemente el MCD sería más pequeño, y va en contra de lo que estamos buscando.

Si lo piensas un poco, para que la división entre a y b con su MCD dé como resultado 1 y 2 se debe cumplir que:

b = 2 × a

Es decir, que de nuestra pareja de números, uno será el doble que el otro por lo que el mayor deberá ser par. Y de hecho, el MCD será la mitad de ese número mayor. Esto es importante, porque dado que lo que queremos es conseguir el mayor MCD, tendremos que buscar en el rango el mayor número par; y la mitad será el MCD que nos están pidiendo.

¿Qué significa esto? Que la solución al acertijo es, simplemente, la mitad del número mayor del rango, teniendo cuidado si es un impar, para hacer división entera 🙂 El resultado es que las soluciones a nuestras tres preguntas eran 5, 500 y 49.999.

Iván intuyó que el número 2 era importante, y ¡así es! Pero no se pueden usar las potencias. De hecho, su solución no era válida para el ejemplo… Con la tabla, vimos que el mayor MCD era el 2, y sin embargo, la mayor potencia de 2 entre 1 y 5 es el 4 (2²) 🙂 ¡Seguro que el próximo lo resuelves bien!

Mientras llega, podéis programar la solución y probarla aquí.

¡Hasta el próximo!

El mayor máximo común divisor

by

¡Hola, mentes inquietas!

Inicio de semana y estreno de acertijo. Esta vez vamos a hablar del máximo común divisor, o MCD. Como muchos sabréis, el MCD de dos números A y B es el mayor número que divide simultáneamente a ambos números, A y B. Os ponemos varios ejemplos:

  • MCD(8, 4) = 4
  • MCD(8, 6) = 2
  • MCD(9, 5) = 1

Seguro que recuerdas la forma de calcularlo: si descompones los números en factores primos, el MCD son aquellos comunes elevados al menor exponente. Para programarlo, es mucho más fácil y rápido usar el algoritmo de Euclides.

Si se calcula el MCD de todas las parejas que se forman con los números (distintos) entre 1 y 5 sale la siguiente tabla:

1 2 3 4 5
1
2 1
3 1 1
4 1 2 1
5 1 1 1 1

Se ve que el mayor MCD de todos tiene el valor 2. ¿Cuál es el mayor MCD de todas las parejas que se pueden formar con los números de 1 a 10? ¿Y de 1 a 100? ¿Y a 99999?

Como siempre, si das con la solución y la programas, puedes probarla aquí.

¡Hasta el domingo!

Solución: sin dos bits a uno

by

¡Hola!

Os pedimos disculpas por haber pasado una “semana en blanco” sin acertijo. Como muchos sabéis, el miércoles tuvo lugar el regional de Madrid de ProgramaMe, el concurso de programación para ciclos formativos, y no hemos tenido un momento libre.

¡Pero ya hemos vuelto! Empezamos hoy resolviendo el acertijo que os poníamos hace dos semanas. Estaba, como el anterior, relacionado con números binarios. En concreto, os preguntábamos cuántos números de 4, 10 y 24 bits no tienen una sucesión de dos bits a uno. jserra nos envió el código fuente para resolverlo pero… ¡esta vez no acertó! En el ejemplo que os poníamos, de 3 bits, salen 8 posibles combinaciones, y de esas 8, veíamos que había 5 que no tenía 2 bits consecutivos a 1. Sin embargo, la respuesta de jserra dice que hay… 12. ¡Eso son más que el número de combinaciones en primer lugar! Por tanto algo parece no funcionar…

Gualterio dio la respuesta a las tres preguntas que os hacíamos, del número de combinaciones de 4, 10 y 24 bits sin dos consecutivos a 1. Aseguró que son 8, 144 y 121393 y…. ¡acertó! Iván (¡bienvenido!, sí, deberías haber participado como profe :-p) nos dio su esbozo de la solución pero… parece que le falta el caso base 🙂 a si es que no está del todo claro si está bien o no.

Veamos nuestra solución. Ya os contábamos que lo interesante era conseguir dar la respuesta sin construir todos los números y analizar cada uno para ver si tenía o no dos bits a 1. Por tanto, hay que pensar un poco y tratar de construir los números válidos directamente.

Para eso, empezamos con un único bit. Las posibles combinaciones son 0 y 1, y ambas son válidas, pues ninguna tiene, obviamente, dos bits a 1.

Vamos con dos bits. Para eso, comenzamos con las posibilidades correctas de un único bit, y añadimos un segundo a la derecha:

  • A la configuración de un bit “0” podemos añadirle o bien un 0 o bien un 1 y seguirá siendo una combinación válida.
  • A la configuración de un bit “1” tenemos obligatoriamente que añadirle un 0. Si le añadiéramos un 1 tendríamos dos bits a 1 seguidos.

Vemos que con dos bits por tanto, tenemos tres configuraciones posibles, 00, 01 y 10.

Si damos el salto a tres bits:

  • A las configuraciones 00 y 10 podemos añadirle tanto un 0 como un 1 (recuerda que siempre añadimos por la derecha), y ambas serán configuraciones correctas.
  • A la configuración 01 sólo podemos añadirle un 0.

Por lo tanto, las configuraciones válidas son 000, 001, 100, 101 y 010, las 5 que anticipábamos en el enunciado.

La conclusión que debemos sacar de aquí es que lo importante para el siguiente paso (n+1 bits) es saber cuántas configuraciones válidas de n bits (paso anterior) acaban con 0 o con 1. Por cada configuración acabada en 0 tendremos dos configuraciones posibles de n+1 bits (la original, añadiendo por tanto un 0 y un 1). Por cada configuración acabada con 1 tendremos sólo una (la original, añadiendo un 0).

Además, pensando en los siguientes pasos, es importante recordar, de las nuevas configuraciones, cuántas acabarán en 0 y cuántas en 1. Dado que a las configuraciones de n bits acabadas en 0 las hemos añadido un 1, el número de configuraciones de n+1 bits acabadas en 1 será el de las acabadas en 0 con n bits. Por su parte, el número de configuraciones acabadas en 0 es la suma de las que había antes, pues a todas las configuraciones le podemos siempre añadir un 0.

Es decir:

configuracionesEn0(n+1) = configuraciones(n)
configuracionesEn1(n+1) = configuracionesEn0(n)
configuraciones(n) = configuracionesEn0(n+1) + configuracionesEn1(n+1)

Si nos pintamos una tabla:

# bits conf. en 0 conf. en 1 Conf. totales
1 1 1 2
2 2 1 3
3 3 2 5
4 5 3 8
5 8 5 13

¿Os suena? ¡¡Son los números de Fibonacci que ya han aparecido otras veces en nuestros acertijos!! Efectivamente, el número de combinaciones de n bits sin dos bits a 1 es el número de Fibonacci n-2 (asumiendo que empezamos la secuencia con 1, 1, 2, …). Curioso, ¿¡verdad!? 🙂

Como siempre, si programas tu solución puedes probarla aquí.

¡Hasta el próximo!

Sin dos bits a uno

by

Hola!

Vamos esta semana a aprovechar el calentamiento con el acertijo de la semana pasada para proponeros otro que también está relacionado con bits.

Si escribimos todos los números posibles con 3 bits, obtenemos los siguientes posibles 8 valores:

000 001 010 011 100 101 110 111

En cursiva se han resaltado 5 configuraciones; como quizá alguno se haya dado cuenta, son las configuraciones que no tienen una pareja de unos consecutiva. Los otros tres (011, 110 y 111) tienen al menos dos bits a 1 consecutivos.

Seguro que os imagináis la pregunta que viene ahora… ¿cuántas configuraciones existen de 4 bits que no tengan dos bits consecutivos a 1? ¿Y de 10 bits? ¿Y de 24?

Teniendo paciencia, es posible que que lleguéis a la respuesta de 4 o 10 bits. Si programáis, podéis quizá resolver la de 24 probando todas las opciones y contando. Pero… ¿sois capaces de encontrar una forma de responder a las preguntas usando como mucho una calculadora tradicional? 🙂

Sea como sea, si dais con la respuesta, ¡contádnosla! Y, como siempre, para los que la programéis, podéis probarla aquí.

¡Hasta el domingo!