[Variante di un problema di enomis]
Supponiamo di avere una griglia di nxn punti. Coloriamo questi punti con quattro colori in modo che ogni "quadratino" abbia i vertici di colori differenti (spero che si intenda cosa voglia dire con "quadratino"). Quante griglie siffatte esistono?
Colorazione di griglie
-
Aethelmyth
- Messaggi: 47
- Iscritto il: 16 ago 2006, 19:24
- Località: Roma Eur, Torrino
- Contatta:
-
Aethelmyth
- Messaggi: 47
- Iscritto il: 16 ago 2006, 19:24
- Località: Roma Eur, Torrino
- Contatta:
]. Mi piacerebbe sentire la soluzione 
.Stanotte alle 4.00 (sarebbe piu' corretto parlare di stamattina...) ho trovato un metodo semplice semplice per risolvere il problema... Stanotte lo posto. (No, non e' che vivo di notte, e' che dopo essere uscito ed essere tornato a casa dopo la serata, non ho mai sonno ed allora scarabocchio sui fogli..)
Ci sono due tipi di griglie: quelle che hanno la prima riga di 2 colori, e quelle che hanno la prima riga di almeno 3 colori.
Lemma: La riga sottostante ad una con 2 colori ha 2 colori. La riga sottostante ad una con almeno 3 colori, ha almeno 3 colori.
Dim: Una riga con due colori ha necessariamente il pattern ABAB...
$ \begin{matrix} \ldots & A & B & A & \ldots \\ \ldots & x_1 & x_2 & x_3 & \ldots \end{matrix} $
Imponendo $ x_2=C, $ si hanno forzatamente $ x_1=x_3=D, $ e cosi' via definendo tutta la riga a partire da $ x_2=C. $
Se una riga ha tre colori, esiste un punto con un pattern ABC:
$ \begin{matrix} \ldots & A & B & C & \ldots \\ \ldots & x_1 & x_2 & x_3 & \ldots \end{matrix} $
Si ha obbligatoriamente $ x_2=D, $ e $ x_1=C, x_3=A, $ quindi anche la riga sottostante e' di almeno 3 colori e puo' essere scelta in unico modo, e cosi' via per tutte le altre righe ad essa sottostanti.
Quindi il numero di scacchiere ammissibili e' data dalla somma delle scacchiere con 2 colori in prima riga e dalle scacchiere con almeno 3 colori in prima riga.
Quelle con due colori hanno in ogni riga un pattern del tipo ABABA.... con quattro colori le prime righe possibili diventano 12, ovvero scelgo due colori tra quattro e l'ordine conta, la seconda la scegliamo in 2 modi, la terza in 2 modi e cosi' via, quindi $ 4\times3\times2^{n-1}=4!\times2^{n-2} $ scacchiere ammissibili siffatte.
Per quanto visto prima la scacchiera con almeno 3 colori in prima riga e' univocamente determinata dalla prima riga, quindi il numero di queste scacchiere equivale il numero delle stringhe su alfabeto quaternario composte da almeno tre di queste lettere e senza due lettere uguali vicine; 4 modi per scegliere la prima lettera, 3 modi per scegliere la seconda, 3 per la terza e cosi' via, ovvero $ 4\times 3^{n-1}; $ cosi' facendo contiamo anche le righe di due soli colori, che sono 12. Quindi abbiamo che la soluzione e'
$ 12(2^{n-1}+3^{n-2}-1) $
Lemma: La riga sottostante ad una con 2 colori ha 2 colori. La riga sottostante ad una con almeno 3 colori, ha almeno 3 colori.
Dim: Una riga con due colori ha necessariamente il pattern ABAB...
$ \begin{matrix} \ldots & A & B & A & \ldots \\ \ldots & x_1 & x_2 & x_3 & \ldots \end{matrix} $
Imponendo $ x_2=C, $ si hanno forzatamente $ x_1=x_3=D, $ e cosi' via definendo tutta la riga a partire da $ x_2=C. $
Se una riga ha tre colori, esiste un punto con un pattern ABC:
$ \begin{matrix} \ldots & A & B & C & \ldots \\ \ldots & x_1 & x_2 & x_3 & \ldots \end{matrix} $
Si ha obbligatoriamente $ x_2=D, $ e $ x_1=C, x_3=A, $ quindi anche la riga sottostante e' di almeno 3 colori e puo' essere scelta in unico modo, e cosi' via per tutte le altre righe ad essa sottostanti.
Quindi il numero di scacchiere ammissibili e' data dalla somma delle scacchiere con 2 colori in prima riga e dalle scacchiere con almeno 3 colori in prima riga.
Quelle con due colori hanno in ogni riga un pattern del tipo ABABA.... con quattro colori le prime righe possibili diventano 12, ovvero scelgo due colori tra quattro e l'ordine conta, la seconda la scegliamo in 2 modi, la terza in 2 modi e cosi' via, quindi $ 4\times3\times2^{n-1}=4!\times2^{n-2} $ scacchiere ammissibili siffatte.
Per quanto visto prima la scacchiera con almeno 3 colori in prima riga e' univocamente determinata dalla prima riga, quindi il numero di queste scacchiere equivale il numero delle stringhe su alfabeto quaternario composte da almeno tre di queste lettere e senza due lettere uguali vicine; 4 modi per scegliere la prima lettera, 3 modi per scegliere la seconda, 3 per la terza e cosi' via, ovvero $ 4\times 3^{n-1}; $ cosi' facendo contiamo anche le righe di due soli colori, che sono 12. Quindi abbiamo che la soluzione e'
$ 12(2^{n-1}+3^{n-2}-1) $
Rapidi controlli:
Griglia $ 2\times2: $
$ \left[\begin{matrix} A & B \\ C & D \end{matrix}\right]\times 4! $
Totali = 24.
Previsti = $ 12(2^1+3^0-1) $ = 24.
Griglia $ 3\times3: $
$ \left[\begin{matrix} A & B & A \\ C & D & C \\ A & B & A \end{matrix}\right]\times 4!, \qquad \left[\begin{matrix} A & B & A \\ C & D & C \\ B & A & B \end{matrix}\right]\times 4!, \qquad \left[\begin{matrix} A & B & C\\ C & D & A\\ A & B & C \end{matrix}\right]\times 4!, $
Totali = 72
Previsti = $ 12(2^2+3^1-1) $ = 72
Una griglia $ n\times m, $ ha $ 12(2^{n-1}+3^{m-2}-1) $ colorazioni ammissibili.
Griglia $ 2\times2: $
$ \left[\begin{matrix} A & B \\ C & D \end{matrix}\right]\times 4! $
Totali = 24.
Previsti = $ 12(2^1+3^0-1) $ = 24.
Griglia $ 3\times3: $
$ \left[\begin{matrix} A & B & A \\ C & D & C \\ A & B & A \end{matrix}\right]\times 4!, \qquad \left[\begin{matrix} A & B & A \\ C & D & C \\ B & A & B \end{matrix}\right]\times 4!, \qquad \left[\begin{matrix} A & B & C\\ C & D & A\\ A & B & C \end{matrix}\right]\times 4!, $
Totali = 72
Previsti = $ 12(2^2+3^1-1) $ = 72
Una griglia $ n\times m, $ ha $ 12(2^{n-1}+3^{m-2}-1) $ colorazioni ammissibili.