Nessun volenteroso si è fatto avanti, ma ho trovato la dimostrazione del lemma. Do quindi la mia risposta, mettendola in due spoiler distinti: nel primo metto la soluzione del problema usando il lemma e nel secondo do la dimostrazione del lemma.
Testo nascosto, fai click qui per vederlo
Le regole date rendono la colorazione delle caselle pari indipendente dalle dispari; cominciamo quindi a studiare le sole pari. Accostandole fra loro, si ha una fila di infinite caselle, che si ripetono con periodicità 9, ed occorre che non ci siano due verdi consecutivi; con questa limitazione vediamo come si possono colorare le prime 9 caselle.
Trascurando la periodicità, abbiamo $n=9$ caselle da colorare ed il lemma dice quante colorazioni sono possibili per ogni $k$ verdi; basta quindi sommare i valori relativi alle varie $k$. Otteniamo
$((10),(0))+ ((9),(1))+...+((5),(5))=...=89$
La periodicità esclude che siano contemporaneamente verdi la prima e l'ultima; in questo caso sono blu la seconda e la penultima e restano $n=5$ caselle. Col precedente ragionamento, i modi per colorarle sono
$((6),(0))+((5),(1))+((4),(2))+((3),(3))=...=14$
Le caselle pari possono quindi essere colorate in $89-14=75$ modi. Altrettanto vale per le dispari, e poiché ogni pari può accompagnarsi con ogni dispari, la soluzione è $75^2=5625$
Dimostrazione del lemma
Testo nascosto, fai click qui per vederlo
Con $n$ caselle, ci cui $b$ blu e $k$ verdi, per non avere due verdi consecutivi occorre e basta che ogni verde sia collocato immediatamente dopo ad un blu oppure all'inizio. Ci sono quindi $b+1$ posizioni possibili e dobbiamo sceglierne $k$; i modi per farlo sono $C_(b+1,k)=((b+1),(k))$. Poiché $b=n-k$, abbiamo la tesi.
- Indicando i metri con m e i centimetri con cm, si ha m=100 cm. Quindi 5 centimetri equivalgono a metri m=100*5=500.
- E' disonesto che un disonesto si comporti in modo onesto (R. Powell)