Caselle colorate
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:
[list=1][*:11v113qv] la casella $n$ e la $n+18$ hanno lo stesso colore;
[/*:m:11v113qv]
[*:11v113qv] se la casella $n$ è verde, la casella $n+2$ è blu.[/*:m:11v113qv][/list:o:11v113qv]
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).
[asvg]xmin=0; xmax=6; ymin=-0.5; ymax=5.5;
noaxes();
rect([0,0],[6,5]);
rect([1,1],[5,4]);
line([1,0], [1, 1]); line([1,4],[1,5]); line([2,0], [2, 1]); line([2,4],[2,5]); line([3,0], [3, 1]); line([3,4],[3,5]); line([4,0], [4, 1]); line([4,4],[4,5]); line([5,0], [5, 1]); line([5,4],[5,5]);
line([0,1],[1,1]); line([5,1],[6,1]); line([0,2],[1,2]); line([5,2],[6,2]); line([0,3],[1,3]); line([5,3],[6,3]); line([0,4],[1,4]); line([5,4],[6,4]);
text([0.5,0.5],"0"); text([1.5,0.5],"1"); text([2.5,0.5],"2"); text([0.5,2.5],"16"); text([0.5,1.5],"17"); text([3.5,0.5],"..."); text([0.5,3.5],"...");[/asvg]
Ma il conteggio è palloso assai, anche per l'asimmetria che c'è tra verde e blu... Qualche idea?
Le caselle vanno colorate seguendo solo due regole:
[list=1][*:11v113qv] la casella $n$ e la $n+18$ hanno lo stesso colore;
[/*:m:11v113qv]
[*:11v113qv] se la casella $n$ è verde, la casella $n+2$ è blu.[/*:m:11v113qv][/list:o:11v113qv]
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).
[asvg]xmin=0; xmax=6; ymin=-0.5; ymax=5.5;
noaxes();
rect([0,0],[6,5]);
rect([1,1],[5,4]);
line([1,0], [1, 1]); line([1,4],[1,5]); line([2,0], [2, 1]); line([2,4],[2,5]); line([3,0], [3, 1]); line([3,4],[3,5]); line([4,0], [4, 1]); line([4,4],[4,5]); line([5,0], [5, 1]); line([5,4],[5,5]);
line([0,1],[1,1]); line([5,1],[6,1]); line([0,2],[1,2]); line([5,2],[6,2]); line([0,3],[1,3]); line([5,3],[6,3]); line([0,4],[1,4]); line([5,4],[6,4]);
text([0.5,0.5],"0"); text([1.5,0.5],"1"); text([2.5,0.5],"2"); text([0.5,2.5],"16"); text([0.5,1.5],"17"); text([3.5,0.5],"..."); text([0.5,3.5],"...");[/asvg]
Ma il conteggio è palloso assai, anche per l'asimmetria che c'è tra verde e blu... Qualche idea?
Risposte
Ma non è così palloso dai
EDIT: NO è sbagliato sto contando troppe cose! Hai ragione è palloso
EDIT: NO è sbagliato sto contando troppe cose! Hai ragione è palloso

Non riesco a completare il ragionamento, anche perché oggi ho poca lucidità; penso però che possa essere utile vedere ul mio approccio.
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.
https://www.matematicamente.it/forum/vi ... e#p8391739
adesso non ho troppo tempo.
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$
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$
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.
Dimostrazione del lemma
Dimostrazione del lemma