$6 xx 6$

[axpgn]

Usando $18$ tessere del domino dalle dimensioni di $2 xx 1$, compongo un quadrato dalle dimensioni di $6 xx 6$

Mostrare che, qualsiasi sia la disposizione delle tessere, esiste sempre almeno una linea (orizzontale o verticale) che separa il quadrato in due parti senza che questa linea tagli alcuna tessera.

Per esempio:

Cordialmente, Alex

[Studente Anonimo]

Mi stavo impappinando in una roba un po' difficilina con matrici e mica matrici... poi mi sono reso conto che basta osservare che se una tessera di domino verticale taglia una linea orizzontale allora deve essercene almeno un'altra di tessera verticale che taglia la medesima linea altrimenti non potremmo completare la riga con le tessere orizzontali poiché \(6-1 = 5\) che non è divisibile per \(2\). Dunque se tutte le linee orizzontali sono tagliate da almeno una tessera abbiamo in realtà che tutte le linee orizzontali sono tagliate da almeno due tessere per un minimo di \(5 \cdot 2 = 10 \) tessere verticali. Per simmetria lo stesso discorso vale anche per le tessere orizzontali e le linee verticali. Dunque avremmo almeno \( 20 > 18 \) tessere del domino. Assurdo.

[Studente Anonimo]

Il mio struso iniziale però... mi ha portato a una cosa interessante

Coloriamo in modo alternato (come una scacchiera degli scacchi) il nostro quadrato di \(6 \times 6 \) con il bianco ed il nero (o altri colori se preferite). Scegliamo una numerazione \(n\) di tutte le caselle bianche dal \(1 \) al \(18\) e poi tutte le caselle nere sempre dal \(1 \) al \(18\) in modo arbitrario. Fissiamo un tesseramento \(t\) del rettangolo con le tessere del domino. Chiaramente una singola tessera del domino ricopre sia una casella bianca che una nera. Creiamo una matrice \( A(t,n)= (A(t,n)_{ij})_{1 \leq i,j \leq 18}\), \(18\times 18 \) che dipende chiaramente dal tesseramento e dalla numerazione scelta. Infatti la riempiamo nel seguente modo:
- Se il domino è posizionato orizzontalmente e copre le caselle numerate \( (j,i) \). Allora se \(j\) è nero poniamo \( A(t,n)_{ji} = 1 \), se \(j\) è bianco poniamo \( A(t,n)_{ij}=1 \).
- Se il domino è posizionato verticalmente e copre le caselle numerate \( (k,r) \). Allora se \(k\) è nero poniamo \( A(t,n)_{kr} = i \), se \(k\) è bianco poniamo \( A(t,n)_{rk}=i \), dove \(i \) è tale che \(i^2 = -1 \).
- Tutte le altre entrate della matrice sono riempite con lo zero.

Si può dimostrare quanto segue (credo)
1) Fissiamo \(n\) arbitrario, allora per ogni \(t\) abbiamo che \( \left| \operatorname{det}( A(n,t) ) \right| = 1 \).
2) Sia \(T =\{ t : t \text{ è un tesseramento con il domino del nostro quadrato} \} \) allora per ogni \(n \) abbiamo che
\[ \operatorname{det} \left( \sum_{t \in T} A(t,n) \right) = \operatorname{card}(T) \]

Quindi le matrici costruite in questo modo sono delle matrici rendono il determinante quasi lineare, infatti
\[ \operatorname{det} \left( \sum_{t \in T} A(t,n) \right) = \sum_{t \in T} \left| \operatorname{det}( A(n,t) ) \right| \]

Chiaramente il risultato è indipendente dalla dimensione del quadrato iniziale.

[Studente Anonimo]

"3m0o":

2) Sia \(T =\{ t : t \text{ è un tesseramento con il domino del nostro quadrato} \} \) allora per ogni \(n \) abbiamo che
\[ \operatorname{det} \left( \sum_{t \in T} A(t,n) \right) = \operatorname{card}(T) \]

Quindi le matrici costruite in questo modo sono delle matrici rendono il determinante quasi lineare, infatti
\[ \operatorname{det} \left( \sum_{t \in T} A(t,n) \right) = \sum_{t \in T} \left| \operatorname{det}( A(n,t) ) \right| \]

No ecco ho sbagliato a formalizzare quello che ho pensato. Non intendevo la somma di tutte le matrici. Più che altri cambiamo la matrice nel senso che mettiamo tutti gli 1 possibili e tuttle le \(i\) possibili per formare una matrice \(B\) che dipende solo dalla numerazione e allora lì si abbiamo che \( \left| \det B \right| = \operatorname{card} T\)
Ad esempio se abbiamo un quadrato \(2 \times 2 \) e numeriamo
1 1
2 2
Allora la matrice \(B \) diventa
\[ B = \begin{pmatrix}
1 &i \\
i &1
\end{pmatrix} \]
e abbiamo che \( \det B = 2 \)

[axpgn]

Ça va sans dire ... che l'ho risolto come nel tuo primo messaggio, per il resto non ci ho capito niente

Cordialmente, Alex

[Studente Anonimo]

Per l'altra cosa sulle matrici prendiamo una scacchiera 4x4 per semplicità e numeriamo in questo modo la scacchiera
1 1 2 2
3 3 4 4
5 5 6 6
7 7 8 8

Se ricopri la scacchiera con tessere solo orizzontali allora avrai una tessera che copre le caselle 1 1, una tessera che copre le caselle 2 2 , etc Quindi ci scrivi la matrice
\[ A = \begin{pmatrix}
1 & 0&0 &0 & 0 & 0 & 0 &0 \\
0&1 & 0& 0& 0& 0& 0& 0\\
0& 0&1 & 0& 0 & 0 & 0 &0 \\
0& 0&0 &1 & 0& 0& 0&0 \\
0& 0& 0& 0&1 & 0& 0&0 \\
0& 0& 0& 0&0 &1 & 0& 0\\
0& 0& 0& 0& 0& 0&1 &0 \\
0&0 & 0&0 & 0&0 &0 &1
\end{pmatrix} \]

se invece fai caselle tutte verticali hai le domino che coprono 1 3, (dove 1 è bianco e 3 nero) e una tessera che copra 1 3 8dove 1 è nero e 3 bianco), una tessera che copre 2 4, etc...allora ci fai la matrice
\[ A = \begin{pmatrix}
0 & 0&i &0 & 0 & 0 & 0 &0 \\
0&0 & 0& i& 0& 0& 0& 0\\
i& 0&0 & 0& 0 & 0 & 0 &0 \\
0& i&0 &0 & 0& 0& 0&0 \\
0& 0& 0& 0&0 & 0& i&0 \\
0& 0& 0& 0&0 &0 & 0& i\\
0& 0& 0& 0& i& 0&0 &0 \\
0&0 & 0&0 & 0&i &0 &0
\end{pmatrix} \]

Per ogni modo che hai di ricoprire il quadrato con tessere del domino puoi numerare le caselle in modo tale che la tua matrice sia sempre diagonale e quindi hai
\[ A = \begin{pmatrix}
a_{11} & 0&0 &0 & 0 & 0 & 0 &0 \\
0&a_{22} & 0& 0& 0& 0& 0& 0\\
0& 0&a_{33} & 0& 0 & 0 & 0 &0 \\
0& 0&0 &a_{44} & 0& 0& 0&0 \\
0& 0& 0& 0&a_{55} & 0& 0&0 \\
0& 0& 0& 0&0 &a_{66} & 0& 0\\
0& 0& 0& 0& 0& 0&a_{77} &0 \\
0&0 & 0&0 & 0&0 &0 &a_{88}
\end{pmatrix} \]
dove per ogni \( 1 \leq j \leq 8 \) hai che \( a_{jj} \in \{ 1,i \} \) pertanto hai che
\[ \det A \in \{ -1,1,i, -i \} \]
E siccome cambiare numerazione equivale a scambiare colonne o righe allora per ogni numerazione del quadrato e per ogni modo di coprire il quadrato con le tessere del domino il determinate della matrice associata è di modulo uguale a \(1\).


Mentre per quanto riguarda l'altra cosa intendevo questo: sempre con la numerazione data all'inizio
per ogni tessere del domino che puoi mettere orizzontale ci metti un 1 nella matrice. Per ogni tessera che puoi mettere in verticale ci metti una \(i\) nella matrice. Allora la matrice diventa
\[ B = \begin{pmatrix}
1 & 0&i &0 & 0 & 0 & 0 &0 \\
1&1 & 0& i& 0& 0& 0& 0\\
i& 0&1 & 1& i & 0 & 0 &0 \\
0& i&0 &1 & 0& i& 0&0 \\
0& 0& i& 0&1 & 0& i&0 \\
0& 0& 0& i&1 &1 & 0& i\\
0& 0& 0& 0& i& 0&1 &1 \\
0&0 & 0&0 & 0&i &0 &1
\end{pmatrix} \]
e abbiamo che
\[ \det B = 36 \]
quindi ci sono 36 modi differenti di coprire un quadrato 4x4 con 8 tessere del domino.