Scacchiera

[axpgn]

Se da una normale scacchiera $8 xx 8$ con caselle bianche e nere alternate, togliamo una casella d'angolo e quella all'angolo opposto, si può notare che non è possibile ricoprire le $62$ caselle rimaste con $31$ tessere del domino di dimensioni $2 xx 1$.
Questo perché ogni tessera ricopre sempre una casella nera e una casella bianca ma dato che le due caselle in angoli opposti hanno il medesimo colore, le caselle rimaste saranno $32$ di un colore e $30$ dell'altro.
Se ne può dedurre inoltre che ciò che conta per l'impossibilità, non è la posizione delle caselle rimosse ma il loro colore ovvero lo stesso.
E allora sorge spontanea la domanda: se rimuoviamo una qualsiasi casella bianca ed una qualsiasi casella nera, sarà sempre possibile ricoprire le $62$ caselle rimaste con $31$ tessere del domino di dimensione $2 xx 1$ ?


Cordialmente, Alex

[Drazen77]

L'avevo letta da qualche parte.
Se non ricordo male disegnando un "percorso", dopo aver tolto una casella per colore abbiamo spezzato il percorso in due punti, facendo rimanere il percorso rimanente di lunghezza pari.
Quindi sì, si può sempre.

[axpgn]

Non è sufficiente
Hai tolto due caselle e poi hai trovato un percorso, ma dovresti ripetere questa "prova" per ogni coppia di caselle possibile cioè per $32*32$ volte.
È un po' lunga come dimostrazione sempre ammesso che sia possibile

Cordialmente, Alex

[hydro1]

Sicuramente la soluzione di Drazen77 si può formalizzare, e non c'è bisogno di guardare tutti i casi possibili.

Vi propongo invece una prova per induzione.

Step 1: il problema si può risolvere su una scacchiera $2 imes 2$. La prova è ovvia.

Step 2: il problema si può risolvere su una scacchiera $n imes 2$, per qualsiasi $n$. Prova: penso alle caselle come alle entrate $a_{ij}$ di una matrice $n imes 2$ perchè non ho voglia di fare disegni. Suppongo si possa fare per una $(n-1) imes 2$. Supponiamo che nessuna casella rimossa sia del tipo $a_{1i}$ per $i=1,2$. Allora posso mettere un tile $1 imes 2$ che copre $a_{11}$ e $a_{12}$ e ho finito per l'ipotesi induttiva. Se nessuna casella rimossa è del tipo $a_{ni}$ ho finito per lo stesso motivo. Ma allora l'unico caso che rimane è che entrambe le caselle rimosse siano $a_{1i}$ o $a_{ni}$. Se ne ho rimosse due adiacenti ($a_{11}$ e $a_{12}$ oppure $a_{n1}$ e $a_{n2}$) ho finito di nuovo per ipotesi induttiva. Rimane il caso in cui ho rimosso $a_{1i}$ e $a_{nj}$. Siccome devono avere colore opposto, se $n$ è pari devo aver rimosso due caselle della stessa colonna, mentre se $n$ è dispari devo aver rimosso angoli opposti. In ogni caso c'è un tiling ovvio che copre le caselle restanti.

Step 3: guardo la scacchiera $8 imes 8$. Suppongo induttivamente di poter fare il caso $8 imes n$ per $2leq n<8$. Il passo base è lo step 2. Se almeno un bordo della scacchiera non contiene caselle rimosse, allora posso tagliare una riga (o una colonna) che essendo $8 imes 1$ può essere ricoperta, mentre il resto può essere ricoperto per ipotesi induttiva. Ma allora ogni bordo deve avere una casella rimossa. Ma l'unico modo in cui questo può succedere è che ho rimosso angoli opposti, che è assurdo per ipotesi perchè gli angoli opposti hanno lo stesso colore.

[axpgn]

@hydro

"hydro":Sicuramente la soluzione di Drazen77 si può formalizzare, e non c'è bisogno di guardare tutti i casi possibili.

Appunto. Non ho detto che è errata.

Gli step 1 e 2 ok, mentre lo step 3 non mi è del tutto chiaro; potresti dettagliarlo meglio? Grazie

Cordialmente, Alex

[hydro1]

Pensa alla scacchiera come ad una matrice $8 imes 8$. Ci sono 4 bordi: la colonna $(a_{i1})_{i=1,ldots,8}$, la colonna $(a_{i8})_{i=1,ldots,8}$, la riga $(a_{1i})_{i=1,ldots,8}$ e la riga $(a_{8i})_{i=1,ldots,8}$. Supponi che uno di questi 4 bordi non abbia caselle rimosse. A meno di ruotare la scacchiera, posso supporre che sia la colonna $(a_{i8})_{i=1,ldots,8}$. La taglio via dalla scacchiera, mi rimane una scacchiera $8 imes 7$ con due caselle rimosse che posso ricoprire per ipotesi induttiva; d'altro canto una colonna $8 imes 1$ è ovviamente ricopribile, basta mettere 4 mattoncini in verticale uno dopo l'altro. Quindi ho ricoperto l'intera scacchiera.

Mi rimane da affrontare il caso in cui tutti e 4 i bordi contengono una casella rimossa. Ma se ci pensi un attimo, questo può succedere solo quando ho rimosso due angoli opposti della scacchiera, il che è impossibile per ipotesi. Quindi questo caso non può accadere, e ho finito.

[axpgn]

@hydro
Perdonami ma ho ancora un paio di dubbi ...

"hydro":... mi rimane una scacchiera $ 8 imes 7 $ con due caselle rimosse che posso ricoprire per ipotesi induttiva;

Con i passi precedenti hai dimostrato che è sempre possibile ricoprire le scacchiere $2 xx n$ ma non quelle $3 xx n, 4 xx n, ...$ quindi mi pare che manchi un passaggio prima di poter usare quell'ipotesi induttiva. IMHO

"hydro":Mi rimane da affrontare il caso in cui tutti e 4 i bordi contengono una casella rimossa. Ma se ci pensi un attimo, questo può succedere solo quando ho rimosso due angoli opposti della scacchiera, il che è impossibile per ipotesi. Quindi questo caso non può accadere, e ho finito.

Supponiamo che per la $8 xx 7$ funzioni, aggiungo una colonna da otto e posso avere tre casi: zero o una o due caselle rimosse da questa colonna aggiunta; per zero o due no problem ma se ne tolgo una qualsiasi (non necessariamente l'angolo), l'altra la tolgo dalla $8 xx 7$; come gestisco questo caso?

Cordialmente, Alex

[hydro1]

Hai ragione axpgn, così non funziona. Ma si può aggiustare nella seguente maniera.

Provo per induzione che il problema si risolve su una scacchiera $n imes 2m$ per $n,m$ qualsiasi a patto che $n>1$.

Passo base: il problema si risolve su una scacchiera $2 imes 2m$ per qualsiasi $mgeq 1$. Questo l'ho già provato nel post precedente (lì era $n imes 2$ ma basta ruotare di 90 gradi).

Adesso suppongo il problema si risolva su una scacchiera $n imes 2m$ e guardo una scacchiera $(n+1) imes 2m$, da cui ho rimosso 2 caselle. Questa scacchiera ha un bordo superiore ed uno inferiore, che sono le righe $(a_{1i})_{i=1,ldots,2m}$ e $(a_{(n+1)i})_{i=1,ldots,2m}$. Adesso se nessuna di questa 2 righe contiene caselle rimosse la posso tagliare via. Mi rimane una scacchiera $n imes 2m$ con 2 caselle rimosse che posso ricoprire per ipotesi induttiva più una riga $1 imes 2m$ che posso ricoprire in maniera ovvia.

Mi rimane il caso in cui entrambe queste righe contengono una casella rimossa. Sia $a_{1i}$ la casella rimossa dalla riga superiore. A meno di riflettere la scacchiera rispetto alla verticale che la divide in due metà uguali (che esiste perchè $2m$ è pari), posso assumere che $i$ sia dispari della forma $2k+1$. Adesso tassello la riga superiore in questo modo: metto $k$ tasselli $1 imes 2$ a partire da $a_{11}$ uno dopo l'altro: ho così coperto tutte le caselle $a_{11},ldots,a_{1(i-1)}$. Adesso metto altri tasselli $1 imes 2$ sulla riga superiore uno dopo l'altro a partire da $a_{1(i+2)}$. Così facendo ricopro tutte le caselle $a_{1(i+2)},ldots,a_{1(2m)}$. Mi rimane vuota la casella $a_{1(i+1)}$ nella riga superiore. Allora metto un tassello verticale $2 imes 1$ che la copre, e che necessariamente copre anche $a_{2(i+1)}$. Ora mi dimentico della riga superiore: ho una scacchiera $n imes 2m$ con 2 caselle rimosse: quella della riga inferiore per ipotesi e la casella che è coperta da quell'ultimo tassello $2 imes 1$. Ma il colore di quella casella è uguale a quello di $a_{1i}$, e ho finito ancora per ipotesi induttiva.

[axpgn]

Ieri sera (notte ) avevo pensato una cosa simile ...

Dai passi 1 e 2 sappiamo che una scacchiera $2 xx n$ è sempre ricopribile quindi in particolare una $2 xx 8$.
Supponiamo di aggiungere a quest'ultima una riga da otto.
Se non rimuoviamo caselle da questa riga allora le possiamo rimuovere dalla $2 xx 8$
Se ne rimuoviamo due o i pezzi restanti sono tutti pari e non c'è problema oppure ce ne sono due dispari; in questo caso ricopriamo la casella "spaiata" di ciascun pezzo con un domino la cui altra metà andrà a coprire una casella della $2 xx 8$ ottenendo di fatto una $2 xx 8$ a cui mancano due caselle di colore diverso, di fatto risolvibile.
Se ne rimuoviamo una sola, avremo due pezzi sulla colonna aggiunta, uno pari (no problem) e uno dispari; anche in questo caso posiamo il domino sulla casella spaiata con l'altra metà che copre una casella di colore diverso (ma di colore uguale a quella mancante nella colonna aggiunta); ora basta togliere una casella dalla $2 xx 8$, di colore diverso da quella effettivamente mancante nella colonna aggiunta e (da quella ricoperta dal domino a cavallo) e siamo a posto .
Ok?

Cordialmente, Alex

[marmi1]

Ciao,

ho fatto fatica a seguire la dimostrazione, per cui chiedo venia se il mio ragionamento è simile.
Vedete se questo sta in piedi.

Considero il rettangolo che ha le due case da evitare come vertici.
Il rettangolo avrà un lato con un numero pari di case (p1) e l'altro con un numero dispari (d1),
diciamo sia un rettangolo p1d1. Al limite è un 2 x 1 o un 2n x 1.
Riempio le due file interne adiacenti ai due lati "dispari" con (d1-1)/2 tessere per fila.
Resta da ricoprire un rettangolo p2d1 facilmente ricopribile.
Ora il rettangolo p1d1 è ricoperto (escluse le due case da evitare)
Adiacente, esternamente, ad uno dei lati pari ci deve essere una fila di case, essendo gli altri lati dispari.
Riempio questa fila - per la lunghezza del lato, e ho ricoperto un rettangolo pp (ossia con i due lati "pari"). Se questo ricopre la scacchiera ho finito; altrimenti riempio la fila adiacente a uno dei lati liberi e ottengo un rettangolo pd3.
Iterando ricopro la scacchiera.

Ciao,  
marmi

[axpgn]

Sinceramente, non ho capito ...


Cordialmente, Alex

[marmi1]

Uh, mi sorge il dubbio: forse il quesito e' più complesso di come avevo capito. Le tessera n+1 deve contattare la n ?

Ciao,
marmi

[axpgn]

Non capisco cosa intendi ...

Hai una normale scacchiera ($8 xx 8$) a cui togli una qualsiasi casella bianca e una qualsiasi casella nera; riesci a ricoprire le restanti con le tessere del domino ($(2 xx 1)$?

[marmi1]

Allora provo a spiegare meglio il filo che ho seguito.
spero di utilizzare correttamente le immagini.

Supponiamo che le due case da non ricoprire siano quelle rosse.


Considero il rettangolo formato dalle case gialle e dalle due rosse (le due rosse sono ai vertici).


Il rettangolo ha necessariamente un lato con un numero di case pari e uno dispari.
Nell'esempio le dispari sono in verticale: posso ricoprire i due lati dispari con le tessere:
nell'esempio in verde:


Il resto del rettangolo ha un lato pari, quindi si tassella facilmente: in azzurro nell'esempio:


Ora il rettangolo con i vertici rossi e' completo. La tassellatura in verde. Aggiungo su un lato pari
(deve esistere perché l'altro lato è dispari) una fila di tessere in azzurro.


Ora ho un rettangolo tassellato (in verde) con i due lati che sono numeri pari. Se non ricopre tutta la
scacchiera posso aggiungere una fila (in azzurro) su uno dei lati dove c'è spazio.


Gli ultimi due passi possono essere iterati fino a copertura della scacchiera.

Ciao,
marmi

[axpgn]