un'altra scacchiera

[fraboz]

Sia $ n \geq 2 $ un numero intero. Colariamo tutte le caselle di una scacchiera $ n $x$ n $ in rosso o blu in modo che ogni quadrato $ 2 $x$ 2 $ contenuto nella scacchiera abbia esattamente due caselle blu e due rosse.
Quante sono le colorazioni possibili?

[Valenash]

Notiamo che se in una riga si trovano due caselle adiacenti colorate allo stesso modo, allora tutta la colonna che ha come base queste due caselle avrà una unica possibilità di colorazione (in quanto le altre due caselle del quadrato 2x2 in cui sono contenuti le due caselle adiacenti con lo stesso colore saranno necessariamente da colorare con l'altro colore, e così via). Chiamiamo una riga (o una colonna) di questo tipo ALTERNATA (in realtà si tratta di due righe o di due colonne adiacenti).
Notiamo inoltre che in una scacchiera ci possono essere o solo righe alternate o solo colonne alternate, non ci possono essere una colonna ed una riga alternate.
Infatti, se capitasse ciò, le due caselle di destra del quadrato 2x2 formato dall'intersezione di riga e colonna alternate dovrebbero avere un colore, ad esempio blu, e le due di sinistra l'altro, quindi rosso.
Allo stesso modo, le caselle sopra dovrebbero avere entrambe lo stesso colore (perchè fan parte di una colonna alternata), ma ciò non è possibile perchè abbiamo appena detto che la casella di destra è blu e l'altra è rossa).
Dunque, possiamo calcolare il numero possibile di colorazioni della griglia finale calcolando quante possibili colorazioni ci sono se nella griglia sono presenti una riga (o una colonna) alternata, due righe (o due colonne) alternate ecc..
Se ci sono 0 righe (o colonne) alternate, abbiamo un solo modo di colorare la scacchiera, ossia come è solitamente colorata una scacchiera normale.
Se c'è una sola riga alternata, abbiamo $n-1$ modi di colorarla, a seconda che questa sia la prima riga, la seconda riga, la terza riga; e se le altre righe non devono avere le caselle adiacenti dello stesso colore, la scelta della colorazione è obbligata.
Se ci son due righe alternate, abbiamo $(n-2)(n-3)/2$ modi, che equivalgono al numero di modi per scegliere le due righe, e le altre scelte son sempre obbligate.
Procedendo allo stesso modo, si arriva a calcolare per ogni numero di righe che presentano le caselle adiacenti dello stesso colore il numero di colorazioni come coefficiente binomiale con $k$ da $1$ a $n-1$ di $n-1$ su $k$.
La somma dei coefficienti binomiali di ciascuna riga del triangolo di Tartaglia è di $2^n$, dunque il risultato "per ora" è $2^{n-1}$.
Dobbiamo moltiplicare questo risultato per 2, poichè possiamo indifferentemente scambiare il blu con il rosso data una colorazione, pertanto ciascuna colorazione precedente può essere anche realizzata invertendo blu e rosso.
Infine, moltiplichiamo ancora una volta per due, poichè nei calcoli precedenti abbiamo considerato se ci son 0 righe alternate, una riga alternata ecc... ma lo stessa cosa avviene se c'è una colonna, due colonne ecc alternate.
Ci accorgiamo infine che abbiamo contato due volte i casi in cui ci son 0 righe o 0 colonne alternate, dunque sottraiamo questo numero (che vale 2, poichè queste sono le due possibili colorazioni della scacchiera "normale", ottenibili l'una dall'altra scambiando i colori).
Risultato:
$2^{n-1} \cdot 2 \cdot 2 - 2 = 2^{n+1} -2$
Spero di non avere detto delle cavolate

EDIT: ho riscritto un po' meglio la soluzione perchè l'avevo fatta di fretta..
e l'ultima texata è venuta male per colpa mia, di Latex non conosco quasi nulla

[fraboz]

esatto ma capita anche a voi che si visualizzi male l'ultima texata? perchè non sembrano all'esponente gli esponenti del 2

[fraboz]

Risultato:
$ 2^{n−1}∙2∙2−2=2^{n+1}−2 $

$ 2 \cdot 2 $ =

Codice: Seleziona tutto

2 \cdot 2

per il "per"