baby problem solving

L'altro giorno al CNR un prof propose a me e colleghi un problema di conteggio assegnato al test di ammissione alla triennale in Matematica della Normale di Pisa:

Dato l'alfabeto {A,B,C,D,E,F}, quante sono le stringhe di 6 lettere contenenti due A consecutive?

La prima soluzione che mi venne presto in mente fu di usare una catena di Markov a tre stati:

• non ho ancora scritto due A consecutive e l'ultima lettera scritta non è A;
• non ho ancora scritto due A consecutive e l'ultima lettera scritta è A;
• ho già scritto due A consecutive.

Scritta la matrice di transizione $T$ e calcolata $T^6$ si ottiene in entrata $T(1,3)$ la probabilità di $\phi$ avere una stringa contenente due A consecutive. Aver capito che cosa significa che "la probabilità è una misura" significa trovare ovvio che il numero cercato è $\phi \times 6^6$. Problem? :)

Il problema era che si stava evidentemente usando un cannone per ammazzare mosche, e con fatica dato che c'erano un pochetto di conti in più di quanto ci si aspetterebbe da un test di problem solving, e non di brute-computing. In metro chiacchierando con l'amico polacco arriva il "ma che idiota!": basta usare il principio di inclusione-esclusione con gli eventi:

• "la prima e seconda lettera sono due A"
• "la prima e terza lettera sono due A"
• blablabla
• "la quinta e sesta lettera sono due A"

Concettualmente ora era quasi ammissibile per un buon cervello fresco di liceo, ma ancora c'era la puzza di "calculemus!".

Poi la sera, leggendo la soluzione di un problemino di Teoria dei Codici anch'esso assegnato alla Normale di recente, mi viene in mente una soluzione ricorsiva:

$\\ \text{Indicando con } a_n \text{ le stringhe di } n \text{ lettere NON contenenti due A consecutive,} \\ \text{e con } a_n^A \text{ e } a_n^{\neg A}\text{ le stringhe NON contenenti due A consecutive che } \\ \text{rispettivamente terminano per A e non terminano per A, è facile vedere che:} \\ a_n=a_n^A+a_n^{\neg A} \\ a_n^A=a_{n-1}^{\neg A} \\ a_n^{\neg A}=5a_{n-1} \\ \text{Da cui si ricava immediatamente che } a_n= 5(a_{n-1}+a_{n-2}) \\ \text{e ''srotolando'' la ricorsione ad albero si ottiene facilmente } \\ a_6=5^4(a_2+a_1)+5^3(3a_2+2a_1)+5^2a_2$

Non ho ancora avuto la spigrizia di cercare la soluzione ufficiale al problema tra i test passati.