Ricoprire la scacchiera

[emanuele.croci]

Ciao,

vi propongo un problema che a me piace molto, la soluzione è semplice e geniale ma ...non facile da trovare se uno non la sa!

Prendo una scacchiera 8x8, proprio quella che si usa per giocare a scacchi, e taglio via 2 caselle situate agli angoli opposti.

Restano quindi 62 caselle disposte come segue:

..XXXXXXX

XXXXXXXX

XXXXXXXX

XXXXXXXX

XXXXXXXX

XXXXXXXX

XXXXXXXX

XXXXXXX..

Prendo dei pezzi del domino (rettangolini) e noto che ogni pezzo copre ESATTAMENTE 2 caselle.

E' possibile con 31 pezzi coprire interamente la scacchiera?

Se SI': scrivere una soluzione

Se NO: DIMOSTRARE che è impossibile

...non è facile, ma se uno lo risolve da molta soddisfazione!

Ciao, Emanuele

Modificato: 22 marzo 2007 da emanuele.croci

[siggo]

Non so se e' una dimostrazione, ma ogni pezzo del domino deve coprire una casella bianca e una nera, perche' non puo' essere messo in diagonale.

Togliendo due caselle nere e visto che il numero e' esatto (31X2=62), secondo me non e' possibile.

[emanuele.croci]

Bravissimo Siggo, hai dato la soluzione giusta!

La cosa particolare di questo problema è che la COLORAZIONE bianco/nera delle caselle, che all'apparenza non serve a niente, è in realtà la chiave per risolverlo.

E con tecniche simili (colorazioni ad hoc) puoi risolvere tutta una classe di altri problemi simili....

Ciao, Emanuele

[manderli]

Bellissimo!

Ma... si potrebbe dimostrare anche che, se elimino due qualsiasi caselle di colore diverso, allora mi sarà SEMPRE possibile ricoprire la scacchiera?

... a me pare di sì...

[emanuele.croci]

Secondo me è dimostrabile, ma non con tecniche di colorazione.

Ad es. io ho pensato di usare una tecnica simile "al vecchio gioco del quindici" (quello dove sposti i tasselli e sposti così il buco).

Cosa faccio:

1) pavimento tutta una scacchiera 8x8 usando dei domino messi in verticale.

2) a questo punto decido che voglio "liberare" 2 caselle di colori diversi.

3) tolgo il pezzo di domino che è sulla prima casella BIANCA (supponiamo che sia alla posizione x,y)

4) vedo che così facendo ho creato un BUCO NERO (ulteriore casella libera). Il mio obiettivo è di spostare il BUCO NERO fino alla 2° casella (m,n) che voglio liberare

5) se sposto un pezzo di domino libero nel buco, ho 2 possibilità:

- lo striscio in verticale: il buco si sposta di 2 posizioni in verticale

- lo ruoto e lo metto orizzontale: il buco si sposta a 45° (cioè di 1 posizione in verticale e 1 in orizzontale, in tutti i modi possibili)

6) così facendo sono in grado di raggiungere qualsiasi casella NERA

7) infatti, supponendo che x,y sia sopra e a sx rispetto a m,n, prima scendo all'incirca fino all'altezza n STRISCIANDO PEZZI, poi mi sposto in diagonale RUOTANDO PEZZI

..con un po' di approssimazione, mi pare dimostrato...

Ciao, Emanuele

[siggo]

Ciao,

secondo me il problema generale puo' essere posto cosi':

- Una "scacchiera" e' composta da nxn quadrati con n>1 (strettamente).

- Ogni quadrato "confina" soltanto con quadrati di colore opposto (i vertici del quadrato non valgono come "confini")

Da dimostrare:

se tolgo in numero di quadrati tale i neri siano uguali ai bianchi senza pregiudicare "l'integrita" della scacchiera (ovvero ogni quadrato deve confinare con almeno un altro quadrato) allora e' sempre possibile ricoprirla con un numero di tessere del domino pari alla meta' dei quadrati

ad es. n=3 (scacchiera dispari) non e' ricopribile (banalmente, e' dispari); se tolgo un quadrato e' SEMPRE ricopribile.

E' vero?

[emanuele.croci]

Ciao Siggo,

Questa mi sembra una via un po' improponibile... innanzitutto ci vuole almeno un'ipotesi che i quadrati residui siano CONNESSI, cioè che si possa PERCORRERE la scacchiera da qualsiasi casella a qualsiasi casella.

Se no ti spezzo la scacchiera in 2 zone ognuna con un numero dispari di caselle e sei fregato.

Inoltre, con qualsiasi ipotesi di partenza, restano sempre situazioni impossibili: ad es. ti lascio in una parte della scacchiera una zona di caselle fatta "a croce latina"... non la potrai mai risolvere.... vedi sotto...

..*

***

..*

..*

..*

Ciao, Emanuele

[siggo]

Ciao,

forse hai ragione, ma nella "croce" che hai proposto e' impossibile che i quadrati bianchi siano uguali a quelli neri e che un quadrato di un colore confini solo con quadrati di altro colore.

[emanuele.croci]

Cioè.... è ovvio che, avendo a disposizione tutto il resto della scacchiera (quindi un sacco di spazio!) faccio in modo che la somma globale dei bianchi e dei neri sia uguale!

Non ti ho fatto la scacchiera completa per semplicità, ma concorderai che in un modo o nell'altro ci salto fuori!

Che un quadrato di un colore confini solo con quelli di un altro: mi basta prendere la colorazione della scacchiera standard ed è sempre vero... qualsiasi sua parte o sottoinsieme rispetta questa regola.

Ciao, Emanuele