Giochi di Archimede triennio 2005 - Problema 23

[ercole]

Propongo la seguente soluzione del problema 23, che mi sembra più semplice della soluzione ufficiale:

Quante parole (anche prive di senso compiuto) di quattro lettere si possono scrivere utilizzando solo le lettere A, B, E, M, O in modo che nessuna delle lettere successive ad una B (andando da sinistra verso destra) sia una M ? (Quindi, ad esempio, ABEB deve essere contata ma OBAM no).

Soluzione. Indico con x(n) le parole di lunghezza n soddisfacenti alla condizione richiesta. Posto:

a(n) =numero di parole di lunghezza n soddisfacenti la condizione contenenti la lettera B

b(n) =numero di parole di lunghezza n soddisfacenti la condizione non contenenti la lettera B

abbiamo (per ogni n) :

x(n) = a(n) + b(n)

x(n+1) = 4 a(n) + 5 b(n) = 4 x(n) + b(n)

Dato che b(n) = 4^n , la successione x(n) soddisfa la seguente relazione ricorsiva:

x(n+1) = x(n) + 4^4

Pertanto risulta

x(1) = 1

x(2) = 24

x(3) = 112

x(4) = 512 = 2^9


Ercole

[Marco]

Bravo Ercole. Funziona. Occhio però a tre piccoli errori di stampa:

x(n+1) = 4 x(n) + 4^n

Pertanto risulta

x(1) = 5

x(2) = 24
[...]

(sennò la ricorrenza non funziona...)

Per il resto, benvenuto sul Forum!!

Ciao. M.

[ercole]

Ringrazio Marco per gli errori di stampa giustamente segnalati.

Ciao
Ercole