Caselle colorate

[gugo82]

Ci sono infinite caselle, identificate coi numeri naturali $0,1,2,3,4, ....$, ognuna delle quali può essere colorata di blu o verde.

Le caselle vanno colorate seguendo solo due regole:

1. la casella $n$ e la $n+18$ hanno lo stesso colore;
   
   
2. se la casella $n$ è verde, la casella $n+2$ è blu.

Quante sono le colorazioni possibili?

***

Chiaramente, c'è una periodicità modulo $18$ per la condizione 1; quindi tutto dipende da come si possono colorare sfruttando la condizione 2 le prime diciotto caselle, cioè quelle che vanno da $0$ a $17$, arrangiate in un circuito chiuso (così da rendere l'idea del ciclo).

        Internet Explorer richiede Adobe SVG Viewer per visualizzare il grafico

Ma il conteggio è palloso assai, anche per l'asimmetria che c'è tra verde e blu... Qualche idea?

[3m0o]

Ma non è così palloso dai

Testo nascosto, fai click qui per vederlo

Abbiamo due cammini indipendenti e identici che sono \(0,2,4,6,8,10,12,14,16\) che poi ritorna a \(0\) e quello shiftato a destra di +1, ovvero \(1,3,5,7,9,11,13,15,17\), inoltre interpreto che se \(16\) è verde allora \(16+2 \equiv 0 \mod 18 \) dev'essere blu e analogamente \(17\) verde implica \(1\) blu.

Chiaramente non possiamo mettere su un singolo cammino più di \(4\) verdi. Inoltre ci sono
1) \( \binom{9}{1} \binom{2}{1} \) modi di mettere \(4\) verdi su un cammino
2) \( \binom{9}{1} \left( \binom{4}{1} \binom{3}{1} + \binom{2}{1} \binom{4}{1} \right) \) modi di mettere \(3\) verdi su un cammino
3) \( \binom{9}{1} \binom{6}{1} \) di mettere \(2\) verdi.
4) \( \binom{9}{1} \) di mettere \(1\) verde.
5) E un modo per mettere \(0\) verdi.
Sommiamo tutto, eleviamo il risultato al quadrato (siccome l'altro cammino è identico e indipendente) e otteniamo il numero di suddette colorazioni.

EDIT: NO è sbagliato sto contando troppe cose! Hai ragione è palloso

[giammaria]

Non riesco a completare il ragionamento, anche perché oggi ho poca lucidità; penso però che possa essere utile vedere ul mio approccio.

Testo nascosto, fai click qui per vederlo

La colorazione delle caselle pari non influenza quella delle dispari, quindi ad ognuna delle prime possiamo abbinare ognuna delle seconde. Se $A$ è il numero delle possibili colorazioni delle caselle pari, la soluzione è $A^2$.
Per calcolare $A$ possiamo pensare di accostare fra loro le 9 caselle pari e chiederci in quanti modi le si possono colorare in modo che non ce ne siano due verdi consecutive, ma qui mi fermo. Non dovrebbero venire numeracci: in assenza di limitazioni, ci sono $2^9=512$ colorazioni possibili, quindi certamente $A<512$.

[3m0o]

Sono abbastanza sicuro che si possa usare il Lemma di Burnside per contare le colorazioni di quello che io ho chiamato cammini (per esempio dei numeri pari) in modo simile a questo

https://www.matematicamente.it/forum/vi ... e#p8391739

adesso non ho troppo tempo.

[giammaria]

Credo di aver trovato la risposta, ma è decisamente lunga; si abbrevierebbe molto se qualche volenteroso dimostrasse in modo veloce il seguente lemma. Non ho la certezza che sia vero, ma è testato per $k$ da 0 a 4.

Lemma. Se una fila di $n$ caselle consecutive viene colorato con $k$ caselle verdi e le restanti blu in modo tale che non ci siano mai due verdi adiacenti, allora il numero di colorazioni possibili è $((n-k+1),(k))$
Naturalmente si suppone $n-k+1>=k->n>=2k-1$

[giammaria]

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.