Skip to content

K bits a uno

by

¡Hola!

¡Caracoles! La semana pasada nos pilló el toro y se pasó en blanco sin acertijo 😦 Sentimos haberos hecho esperar… pero ¡ya estamos aquí! Hemos vuelto para haceros pensar un rato 🙂

Ya os hemos hablado antes de los números binarios. Los hemos usado en torneos de tenis, máquinas de monedas e incluso entrelazados con los números de Fibonacci. Como podéis ver… dan mucho juego… ¡y lo que te rondaré, morena! 🙂 Para demostrarlo… vamos con otra pregunta sobre ellos 😉

Si escribimos, por ejemplo, todos los números de 3 bits obtendremos:

000
001
010
011
100
101
110
111

Podéis ver que entre las 8 opciones disponibles hay 3 que tienen un bit a 1, otras 3 que tienen 2, y 1 que tiene 3.

La pregunta es sencilla: ¿cuántos números de 6 bits tienen exactamente 3 bits a 1? ¿Y cuántos de 8 bits tienen 5?

Si das con la solución… ¡cuéntanosla! Y, como siempre, si eres capaz de programarla, puedes probar tu código aquí. Pero… ¡cuidado! El problema en ‘¡Acepta el reto!’ esconde una sorpresa por los tamaños…

¡Venga que no es difícil!

Anuncios

Solución: recortando una elipse

by

¡Hola!

Se termina la semana y vuestro tiempo para darnos la solución al acertijo que os proponíamos el lunes pasado. En él, os preguntábamos cuál es el máximo número de regiones interiores que se pueden formar en una elipse si colocamos sobre su contorno un determinado número de puntos y pintamos líneas uniendo todos con todos. Como ejemplo, os decíamos que con 2 puntos se formaban 2 regiones, con 3 puntos se formaban 4, y con 4 puntos se formaban 8 regiones.

Concretamente, os preguntábamos cuántas regiones interiores se formaban poniendo 6 y 10 puntos diferentes. Si estáis habituados a los números binarios rápidamente os habréis percatado de que las soluciones de los ejemplos son las potencias de dos: 21, 22 y 23. La intuición podría en ese caso llevaros a pensar que con 6 puntos se formarían 25 regiones (32) y con 10 se formarían 29 (512). Pero… ¡os equivocaríais! De hecho, este acertijo (que se conoce como “el problema del círculo de Moser”) se suele utilizar como una prueba de que sacar conclusiones precipitadas utilizando sólo unos cuántos valores iniciales de una secuencia puede llevar a respuestas incorrectas 🙂

Pero nuestro lector Gualterio, que se está convirtiendo en un asiduo 🙂 no cayó en la trampa. Su respuesta, una vez más, ¡fue la correcta! Efectivamente, con 6 puntos se forman 31 regiones internas, y con 10 se forman 256. Como os decíamos el lunes, llegar a estas soluciones es cuestión de calma y tenacidad (especialmente la de 10 puntos). Pero la pregunta que Gualterio se contestó a sí mismo de una elipse con 100 millones de puntos y un total de 4.166.666.416.666.676.249.999.925.000.001 regiones está fuera del alcance del tiempo de una vida humana, de modo que claramente hay una solución mejor 🙂

La que os contaremos aquí necesitará hacer bastantes cuentas (repetitivas), por lo que, como os contábamos el lunes, es mejor resolverlo con un ordenador. Hay también una solución que puede utilizarse para calcular el resultado de una manera mucho más rápida que podría usarse incluso con una calculadora en unos segundos, pero llegar a ella es más complicado, a si es que, por una vez, nos conformaremos con la solución para programadores 🙂

Vamos allá. Lo primero de lo que hay que darse cuenta es de que cuando pintamos una nueva arista uniendo dos puntos, partimos en dos aquellas regiones por las que pasamos. Por ejemplo, si tenemos dos puntos, la figura que formaremos será similar a la siguiente:

Elipse con dos puntos

Si pensáis que al principio había una única región (ocupando el interior completo de la elipse), al dibujar la linea la región queda dividida en dos partes (no necesariamente iguales, claro). Dicho de otro otro modo, de una región inicial, hemos sacado dos, y por tanto el número de regiones totales se ha incrementado en uno.

Con tres puntos, la situación es similar a la siguiente:

Elipse con tres puntos

Al añadir el tercer punto, hay que pintar dos aristas nuevas, cada una de las cuales divide en dos la única región que atraviesa. Por tanto, cada una incrementa en uno el número de regiones totales, y pasamos de 2 a 4 regiones.

Con cuatro puntos el asunto se pone más emocionante:

Elipse con cuatro puntos

Fijaos en la linea que va del punto superior izquierdo al inferior derecho. Esa linea atraviesa dos regiones pues cruza una arista previa ya existente. Por tanto, significa que divide dos regiones anteriores pasando a formar cuatro más pequeñas. Por tanto, la arista incrementa en dos el número de regiones finales.

La conclusión que hay que sacar de este análisis es que cada nueva linea añade tantas regiones como lineas anteriores atraviese más una. Si lo pensáis un poco no os resultará difícil convenceros.

Por tanto, lo que necesitamos saber es ¿cuál es el número máximo de lineas que cruzarán las lineas nuevas? Para eso, vamos a añadir un quinto punto a la figura anterior, y pintaremos una única diagonal:

Elipse con cinco puntos y solo una arista desde el quinto al tercero

El nuevo punto es el etiquetado como 5, y hemos puesto una única arista, que lo une con el punto 3. Como podéis ver, cruza dos aristas previas (en los puntos a y b). ¿Por qué se corta en dos? Se corta en dos porque la nueva arista deja a un lado un punto, y al otro dos. Como todos los vértices están unidos con todos los demás, eso significa que hay 1×2 (=2) aristas que pasan de un lado hacia el otro, y por tanto, 2 cruces. Eso significa que esa arista genera 3 nuevas regiones internas.

Si en lugar de dibujar la arista uniendo el punto 5 con el 3 hubiéramos pintado la arista uniendo el 5 con el 4, en un lado no habría quedado ningún vértice, y al otro lado habrían quedado 3; 0×3 es 0, por lo que no hay corte de aristas y por tanto la arista 5-4 sólo crea una región nueva, al igual que, podéis comprobarlo, ocurre con la arista 5-1. Por su parte, la arista 5-2 cruza otras dos (como la 5-3), por lo que crea tres regiones más.

Una vez que nos hemos dado cuenta de esto, no es demasiado difícil generalizar. Por ejemplo, si tuviéramos ya colocados 7 puntos y estuviéramos colocando el octavo, tendríamos:

  • Dos diagonales que dejan 0 vértices a un lado y 6 a otro, por lo que ninguna se corta con nada y generan una única región (cada una).
  • Dos diagonales que dejan 1 vértice a un lado y 5 a otro, por lo que se cortan con 1×5 diagonales, y añaden 6 regiones cada una.
  • Dos diagonales que dejan 2 vértices a un lado y 4 a otro, por lo que se cortan con 2×4 diagonales y añaden 8 regiones cada una.
  • Una diagonal que deja 3 vértices a un lado y otros tres a otro, lo que genera 3×3 + 1 regiones nuevas.

¿Veis el patrón? Los que programéis, seguro que seréis capaces de hacer un bucle para realizar este cálculo. Además, esto hay que repetirlo para cada punto nuevo añadido (desde 1 hasta 6 o hasta 10 en nuestras dos preguntas), de modo que se necesitan dos bucles anidados. Si lo hacéis con un poco de cuidado, llegaréis a la solución dada por Gualterio 🙂

Aquellos lectores inclinados hacia las matemáticas (que alguno hay 🙂 ) en lugar de (o, quizá, “además de”) bucles también verán sumatorios. En ese caso, no es demasiado difícil (aunque sí un poco laborioso) escribir y desarrollar los sumatorios para llegar a un polinomio con el que calcular el resultado directamente, sin necesidad de un ordenador que nos ahorre el trabajo tedioso de iterar.

Y… para los matemáticos de verdad… este problema puede resolverse en realidad aprovechándose del invariante topológico de Euler (χ) que relaciona el número de aristas, vértices y caras de poliedros. Para eso, hay que considerar a la figura que estamos construyendo como un grafo planar por lo que su invariante topológico es 2. Usando combinatoria, se puede sacar el número de aristas y de vértices (interiores) que se forman a partir de los n vértices exteriores, y usar la χ de Euler para averiguar el número de caras (regiones interiores).

Pero… a los humanos normales nos sirve la solución de bucles 🙂 Si la programáis, recordad que podéis probar vuestra solución aquí (aunque necesitaréis utilizar enteros de precisión arbitraria).

¡Hasta el próximo!

Recortando una elipse

by

¡Hola!

Esta vez os proponemos un acertijo de geometría. Si dibujamos una elipse y elegimos dos puntos cualesquiera en su contorno, al unir esos dos puntos la elipse queda dividida en dos partes:

Elipse con dos puntos

Si ponemos tres, crearemos 4 partes:

Elipse con tres puntos

El asunto se pone interesante con cuatro puntos. Al unir todos con todos, el número de secciones de la elipse crece considerablemente, y pasamos a tener 8:

Elipse con cuatro puntos

¿En cuántas partes queda dividida como máximo una elipse si elegimos 6 puntos diferentes en su contorno y los unimos todos entre sí? ¿Y si elegimos 10?

Para resolver este acertijo, dependiendo de vuestros conocimientos e inquietudes, tendréis tres opciones:

  • Contestar a las dos preguntas usando lápiz y papel y dedicándole un rato a pintar.
  • Pensar un poco (ayudados de lápiz y papel) y llegar a una forma de programar el cálculo para ahorraros un proceso repetitivo y aburrido.
  • Pensar “un mucho” 🙂 y llegar a una forma de calcular el número con unas cuantas operaciones matemáticas.

Ya sabéis que solemos poner acertijos de este tipo, y nos gusta luego resolverlos con la última opción, de modo que cualquiera (incluso los no programadores) puedan contestar a nuestras preguntas rápidamente. Sin embargo, en esta ocasión, seremos infieles a nuestros propios principios, y nos quedaremos con la segunda opción. Por eso, las preguntas que os hemos hecho son intencionadamente “pequeñas”, para que los no programadores puedan contestarlas manualmente pintando. De otro modo, habríamos sido un poco más brutos, preguntándoos por 50 o por 100 puntos 🙂

Eso sí, como siempre, si encontráis la forma de programarlo, podéis probar vuestras soluciones aquí. Y ¡¡no olvidéis contárnoslo en los comentarios!

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!