Problema:
Una prima versione della codifica Morse aveva due soli simboli: • e –, ma non lo spazio. L’alfabeto aveva 6 lettere, codificate come segue: •, –, ••, •–, –•, – –. In quanti modi possibili si poteva leggere un messaggio di 10 simboli?
Soluzione:
Per risolvere il quesito dato è opportuno partire da casi più semplici per poi proseguire tramite generalizzazione.
Notazione: A=lettere composte da un simbolo, B=lettere composte da due simboli.
Nel caso in cui è presente un solo simbolo esso può essere letto in un unico modo: A.
Nel caso in cui sono presenti due simboli essi possono esser letti in due modi distinti: AA, B.
Nel caso in cui sono presenti tre simboli essi possono esser letti in tre modi distinti: AAA, AB, BA.
Nel caso in cui sono presenti quattro simboli essi possono esser letti in cinque modi possibili: AAAA, BB, AAB, BAA, ABA.
Così via dicendo.
Si ottiene dunque la sequenza $1,2,3,5,8,…,k$ , ove il numero successivo, partendo dal terzo, è la somma dei due precedenti. Ciò può esser dunque riscritto come $S_n=S_{n-1}+S_{n-2}$, ove n rappresenta la posizione del numero $S_n$ nella suddetta sequenza ed è maggiore od uguale a 3.
Poiché il quesito richiede il valore di $S_{10}$, senza calcolare ogni possibile combinazione è possibile ridurre $S_{10}$ in funzione di alcuni $S_n$ più piccoli già noti, ad esempio $S_4=5$ ed $S_5=8$. Si ha dunque
$S_{10}=S_9+S_8=2(S_8)+S_7=2(S_7+S_6)+S_6+S_5=2(2(S_6)+S_5)+S_6+S_5=3(S_5)+5(S_6)=8(S_5)+5(S_4)=8×8+5×5=64+25=89$.
Il numero possibile di letture distinte di un messaggio di 10 simboli risulta dunque essere 89.
Link ufficiale alla prova: https://www.altamatematica.it/wp-content/uploads/2021/03/proveindam2020-21.pdf