Pagina 1 di 1
Quadrati colorati
Inviato: 26 giu 2006, 23:16
da 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.
Inviato: 14 ago 2006, 12:00
da 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....
Inviato: 09 dic 2007, 11:03
da ercole
Catraga ha scritto: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