Quadrati colorati

[enomis_costa88]

Un quadrato (n-1)x(n-1) è diviso in $ (n-1)^2 $ quadratini unitari.
Ciascuno degli $ n^2 $ vertici è colorato di rosso o di blù.
Trovare il numero di colorazioni possibili tali che ciascun piccolo quadratino unitario abbia due vertici di ciascun colore.

Buon lavoro, Simone.

[Catraga]

Nessuno che ci prova? Do degli hints per la soluzione con le ricorrenze...

SPOILER: leggere solo fino all'aiuto necessario!

Hint livello 0: esistono due tipi di scacchiere, quelle con i due vertici in alto a sinistra (in senso orizzontale) dello stesso colore (tipo 2), oppure di colore differente (tipo 1-1).

Hint livello 0.5: cercare di "Guessare l'ansatz" (cercare la risposta) senza guardare gli aiuti successivi.

Hint livello 1: generalizzare ad una griglia $ n\times m $. Chiamare $ a(n,m) $ la quantita' di scacchiere.

Hint livello 2: Fissare $ n $ e considerare la successione $ a_n(m) $.

Hint livello 3: Dividere $ a_n(m)=a^+_n(m)+a^-_n(m) $, dove $ a^+_n(m) $ sono le scacchiere tipo 2, e le altre sono scacchiere tipo 1-1.

Hint livello 4 (soluzione): Considerare le due successioni separatamente impostando le ricorrenze. Imporre $ m $ in modo appropriato.

Sei hai letto fino a qui vuol dire che hai letto tutti gli aiuti e dovrei sgridarti....

[ercole]

Nessuno che ci prova? Do degli hints per la soluzione con le ricorrenze...

SPOILER: leggere solo fino all'aiuto necessario!

Hint livello 0: esistono due tipi di scacchiere, quelle con i due vertici in alto a sinistra (in senso orizzontale) dello stesso colore (tipo 2), oppure di colore differente (tipo 1-1).

Hint livello 0.5: cercare di "Guessare l'ansatz" (cercare la risposta) senza guardare gli aiuti successivi.

Hint livello 1: generalizzare ad una griglia $ n\times m $. Chiamare $ a(n,m) $ la quantita' di scacchiere.

Hint livello 2: Fissare $ n $ e considerare la successione $ a_n(m) $.

Hint livello 3: Dividere $ a_n(m)=a^+_n(m)+a^-_n(m) $, dove $ a^+_n(m) $ sono le scacchiere tipo 2, e le altre sono scacchiere tipo 1-1.

Hint livello 4 (soluzione): Considerare le due successioni separatamente impostando le ricorrenze. Imporre $ m $ in modo appropriato.

Sei hai letto fino a qui vuol dire che hai letto tutti gli aiuti e dovrei sgridarti....

Esiste una soluzione più semplice, senza ricorrenze:

Coloriamo a caso i vertici dell'ultima riga. Tale colorazione può essere di due tipi:

1) vi sono due colori uguali adiacenti (si può fare in $ 2^n-2 $ modi).
Ciascuna delle righe restanti può essere colorata in un sol modo.

2) i colori sono alternati ($ RBRB\ldots $ oppure $ BRBR\ldots $).
Ciascuna delle righe restanti può essere colorata in due modi.

Pertanto il numero di colorazioni possibili è:

$ a_{n}=2^n-2+ 2\cdot 2^{n-1}=2^{n+1}-2 $

Ragionando nello stesso modo si dimostra che ina griglia formata da $ n\times m $ punti può essere colorata in

$ a_{m,n}=2^n+2^m-2 $

modi.

Leon