Problema 10 del concurso Marató de problemes 2024< Se dirige a una edad de: 14-15 años
Un sistema de codificación emplea, para los seis caracteres que se quieren cifrar (a los que llamaremos letras) una codificación de tipo Morse, dos letras se codifican con un símbolo y las otras cuatro con dos cada una. Las codificaciones son ·, -, ··, ·-, -· y –.
Un texto que vayamos a cifrar le llamaremos una palabra. El receptor tiene un trabajo añadido para interpretar un mensaje, porque recibe todos los símbolos seguidos, correctamente ordenados, pero sin separación entre las letras.
Por ejemplo, si recibe ·-, tiene dos posibilidades: una palabra de dos letras formada por · y por -, o bien una palabra de una única letra ·-.
Si recibe el mensaje ··-, tiene tres interpretaciones, empezar por una letra de un símbolo y tener después dos letras de un símbolo cada una, o bien empezar con una letra de un símbolo y tener luego una letra de dos símbolos, o bien empezar con una letra de dos símbolos y seguir después con una de un símbolo.
Si recibes dos símbolos, tiene dos formas de interpretar el mensaje, y si recibe 3, tendría 3 formas de interpretarlo.
¿Sabrías decir al recibir el mensaje –·- cuantas formas tendríamos de interpretarlo?
Preguntas:
Si recibimos los 8 símbolos ·-··–·-, ¿de cuántas formas se puede interpretar el código recibido?
Si los ocho símbolos recibidos fueran otros, como ········ o -·-·-·-· ¿el número de palabras que se pueden interpretar sería el mismo o diferente?

Solución:
Estos problemas se tratan bastante bien por inducción (es decir, estudiando cómo son para un valor y cómo se pasa al siguiente).
Es muy sencillo, viendo todos los casos posibles, que una palabra de un único símbolo tiene una única interpretación, mientras que todas las de dos símbolos tienen dos interpretaciones.
Claramente, una palabra de tres símbolos puede interpretarse como una letra de un símbolo y una palabra de dos símbolos, lo cual tendría dos interpretaciones, o bien como una letra de dos símbolos y una palabra de un único símbolo, que sólo tiene una interpretación. Eso hace un total de tres interpretaciones.
Vayamos con una palabra de cuatro símbolos. Puede que el primer símbolo sea una letra, y en ese caso nos quedarían tres símbolos, que da lugar a tres interpretaciones, o bien puede que los dos primeros símbolos sean una única letra, quedando entonces dos para interpretar, lo que supone dos interpretaciones más.
Eso quiere decir que cuatro letras da lugar a cinco interpretaciones diferentes (3 + 2).
Para este estudio no es necesario diferenciar el tipo de símbolos que recibimos (ya que todas las combinaciones de símbolos tienen las mismas interpretaciones, la situación cambiaría si hubiese combinaciones de uno o de dos símbolos que no tuviesen interpretación).
Para cinco símbolos, haciendo un razonamiento análogo tendríamos 5 + 3 = 8 posibilidades, para seis símbolos tendríamos 8 + 5 = 13, para siete símbolos tendríamos 13 + 8 = 21, y por tanto, en caso de recibir 8 símbolos, como se nos pregunta, tendríamos 21 + 13 = 34 posibilidades de interpretación diferente, y sería así para cualquier combinación de 8 símbolos recibida.