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:

[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 :lol:

giammaria2
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.

giammaria2
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$

giammaria2
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

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.