Newsgroup: it.hobby.enigmi
Titolo: Quadrato di domini

Utilizzando tessere di domino rettangolari 2*1 voglio riempire un quadrato,
in modo tale che ciascuna retta che lo attraversi tagli almeno una tessera.
Ovviamente non e' possibile per il quadrato 2*2
.       ___
. _____|___|_____
.      |___|
in quanto una *mediana* attraversa il quadrato senza tagliare alcuna
tessera.
Con il 3*3 (ed in genere con tutti i quadrati dispari) e' possibile piazzare
le tessere in modo che ciascuna retta ne tagli almeno una
.  ___ _
. |___| |
. | |_|_|
. |_|___|
ma il quadrato non e' riempito (rimane almeno un *buco* in mezzo.
Ora mi chiedo qual e' (se esiste) il quadrato minimo che puo' essere
riempito.
E, se non esiste, perche'?
ciao
paolo

 E, se non esiste, perche'?
S
 p
  o
   i
    l
     e
      r
Non e' difficile dimostrare che un lato deve essere >5 cosi' il primo
candidato e' un 6x6.
Dopo diversi tentativi infruttuosi, proviamo con un ragionamento.
All'interno del quadrato passano 5 linee verticali e 5 orizzontali che
devono essere tutte interrotte da almeno 1 tessera. 
 _ _ _ _a_ _
|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|x|x|_|
|_|_|_|_|_|_|
|_|_|_|_|_|_|
        a
Nell'esempio la tessera xx interrompe la linea aa, ma cosi'la linea aa
lascia ai propri lati due regioni con un numero dispari di quadrati che
ovviamente non possono essere coperte da domino, ne consegue che ogni
linea deve essere interrotta da almeno 2 domino. Le linee sono 10, e
occorrerebbero 20 tessere, ma nel 6x6 ce ne stanno solo 18. Si conclude
che tale costruzione e' impossibile.
Nell'8x8 ci sono 14 linee, col ragionamento appena fatto, occorrono
almeno 28 domino, ma ne abbiamo a disposizionestanno 32, un numero
sufficiente.  Difatti con un po' d'attenzione si trova subito una sol:
 _ _ _ _ _ _ _ _
|_ _|_ _| |_ _| |
| | |_ _|_|_ _|_|
|_|_| |_ _| |_ _|
| | |_|_ _|_| | |
|_|_| | |_ _|_|_|
|_ _|_|_|_ _| | |
| |_ _| | | |_|_|
|_|_ _|_|_|_|_ _|  
:) dario

 E, se non esiste, perche'?
Caspita Paolo, il classico dei classici sei andato a pescare.
8X8 e' il minimo quadrato perfetto (ovvero che puo' essere riempito in modo
che non ci siano linee che lo attraversano senza tagliare alcuna tessera).
6X5 e' il minimo per i rettangoli.
Il quadrato 6X6 non puo' essere riempito. La spiegazione e' tratta dal
solito Gardner:
"Consideriamo un rettangolo di sei per sei coperto interamente di duomini.
Una figura del genere contiene 18 duomini (meta' della superficie) e dieci
linee del reticolato (5 orizzontali e 5 verticali). Essa sarebbe senza
difetti se ogni linea intersecasse almeno un duomino. Il primo passo della
dimostrazione e' di far vedere che, in ogni rettangolo senza linee di
frattura, ogni linea del reticolato deve tagliare un numero *pari* di
duomini. Consideriamo una qualsiasi linea verticale. L'area alla sua
sinistra (espressa in unita' quadrate) e' pari (6, 12, 18, 24 o 30). I
duomini che sono *completamente* sulla sinistra di questa linea devono
anch'essi coprire un'area pari perche' ogni duomino copre due quadratini. I
duomini *tagliati* dalla linea devono anch'essi coprire un'area pari sul
lato sinistro, perche' quest'area e' la differenza di due numeri pari
(l'area totale sulla sinistra e l'area dei duomini non tagliati sulla
sinistra). Dato che ogni duomino tagliato occupa *un* quadrato dalla parte
sinistra della line, vi deve essere un numero *pari* di duomini tagliati
dalla linea del reticolo. Il quadrato di sei per sei ha un reticolato di 10
linee. Per essere senza fratture ogni linea deve intersecare almeno 2
duomini. Ma nessun duomino puo' essere tagliato da piu' di una linea,
percio' almeno venti duomini devono essere tagliati dalle lineee del
reticolato. Ma nel quadrato sei per sei ci sono solo 18 duomini!"
Una soluzione per il 5X6 e' la seguente:
 _ _ _ _ _ _
| |_ _| |_ _|
|_|_ _|_| | |
| | |_ _|_|_|
|_|_| |_ _| |
|_ _|_|_ _|_|
e questa e' una 6X8
 _ _ _ _ _ _ _ _
| |_ _| |_ _|_ _|
|_|_ _|_|_ _| | |
|_ _| |_ _| |_|_|
| | |_|_ _|_|_ _|
|_|_|_ _| |_ _| |
|_ _|_ _|_|_ _|_|
A partire da questi si possono riempire tutti gli n per m di area pari, con
entrambe le dimensioni maggiori di 4, tranne il 6X6. La tecnica e' semplice.
Si parte da un 5X6 o da un 6X8 e si procede ampliando di due una delle
dimensioni. Per fare cio' si spostano di due quadretti i duomini del bordo
inserendo duomini orizzontali per riempire il buco. Ecco un esempio:
 _ _ _ _ _ _      _ _ _ _ _ _ _ _
| |_ _| |_A_|    | |_ _| |_._|_A_|
|_|_ _|_| |B|    |_|_ _|_| |_._|B|
| | |_ _|_|_|===>| | |_ _|_|_._|_|
|_|_| |_ _|C|    |_|_| |_ _|_._|C|
|_ _|_|_ _|_|    |_ _|_|_ _|_._|_|
Ciao, Silv:o)