Scacchiera

[axpgn]

Sia data una scacchiera dalle dimensioni di $(2m+1) xx (2n+1)$ nella quale le quattro caselle d'angolo siano nere.

Dimostrare che se vengono rimosse due caselle nere qualsiasi ed una casella bianca qualsiasi, la scacchiera rimanente può essere interamente ricoperta con tessere del domino (cioè rettangoli $2 xx 1$)


Cordialmente, Alex

[Quinzio]

Si parte dal caso piu' semplice ovvero $m=1, n=1$, ottenendo una scacchiera 3x3.

Le possibili disposizioni sono 4:

xxx xAx xAx xxA
ABC xAB BAC BBA
ABC CCB BxC CCx

Una x indica una casella rimossa e le 3 tessere del domino sono AA, BB e CC.
Ogni altra disposizione si puo' ottenere dalle 4 di base con opportune rotazioni e/o simmetrie.

Scacchiere piu' grandi, di qualsiasi dimensione, si possono ottenere sezionando in due parti, in modo opportuno, una delle 4 disposizioni di base e inserendo le tessere mancanti.
E' da notare che a partire dalla scacchiera 3x3, si ottengono scacchiere piu' grandi inserendo due colonne o due righe accoppiate (attaccate una all'altra), non separate. In questo modo si rispetta la regola che le caselle rimosse devono essere 2 nere e 1 bianca.
A titolo di esempio, si prenda la seconda disposizione e si vogliano inserire 2 colonne tra la 1a e la 2a colonna:

xAx x--Ax xDDAx
xAB x--AB xEEAB
CCB CC--B CCFFB

[axpgn]

"Quinzio":Si parte dal caso piu' semplice ovvero $m=1, n=1$, ottenendo una scacchiera 3x3.

Le possibili disposizioni sono 4:

No. Ovviamente al netto di rotazioni e simmetrie

Cordialmente, Alex

[Quinzio]

"axpgn":[quote="Quinzio"]Si parte dal caso piu' semplice ovvero $m=1, n=1$, ottenendo una scacchiera 3x3.

Le possibili disposizioni sono 4:

No. Ovviamente al netto di rotazioni e simmetrie


Cordialmente, Alex[/quote]

Aspetta... mi riferivo solo alla posizione delle caselle rimosse.

Mi spiego meglio... si prendono le scacchiere 3x3 che ho disegnato prima e si sostituiscono le tessere del domino AA, BB, CC e le si sostituiscono con un simbolo comune.
A questo punto mi sembra che le configurazioni di base siano 4.
Dove sbaglio ?

Rimetto qui le configurazioni con le tessere del domino eliminate

xxx x-x x-x xx-
--- x-- --- ---
--- --- -x- --x

[axpgn]

No, sono più di 4

[Quinzio]

"axpgn":

No, sono più di 4

Ok, chiedo venia, sono 5.
Le visualizzo qui:

xxx x-x x-x xx- xx-
--- x-- --- --- -x-
--- --- -x- --x ---

Comunque sarai d'accordo con me che non ha molta importanza il numero di disposizioni di base.
Potrebbero essere anche 100, quello che conta e' che si possano separare in due parti in modo da essere espanse a piacere.

[axpgn]

Premesso che le combinazioni sono sei

non hai ancora dimostrato la tesi, quello che hai scritto nel primo post è molto vago.
Per esempio, è possibile espandere la prima scacchiera qui sopra inserendo una sola colonna pur rispettando le condizioni richieste ed in tal caso non vale già più la soluzione proposta ma va ripensata; è solo un esempio ma evidenzia che la dimostrazione non è così banale come ti sembra.

Cordialmente, Alex

[Quinzio]

Abbi pazienza e chiedo di nuovo scusa per alcune risposte troppo frettolose.

In effetti le configurazioni sono 6.
Le riporto disegnate qui sotto. Una X significa una casella rimossa.



A questo punto la mia tesi e' che sia abbastanza banale partendo da una scacchiera qualsiasi riportarsi in una delle configurazioni di base, eliminando grosse parti della scacchiera.

Faccio un esempio grafico qui sotto:



Le X sono state poste in modo casuale.
Dalla prima scacchiera alla seconda e' stata eliminata la grossa area ombreggiata.
L'area e' pari, ed e' rettangolare, quindi e' facile tassellarla.
Dalla seconda alla terza scacchiera e' stata eliminata un'altra area tratteggiata.
La terza scacchiera e' gia' facile da ricoprire, ma volendo riportarsi ad una delle configurazioni di base, si eliminano le caselle coperte dalle 3 tessere.
A questo punto siamo arrivati ad una delle 6 configurazioni di base.

Ovviamente questa non e' una dimostrazione rigorosa, anzi, non e' neanche una dimostrazione.
E' un algoritmo (che andrebbe ovviamente specificato meglio) che consente di ridurre/espandere le scacchiere per raggiungere qualsiasi configurazione.

Sarebbe davvero gradito da parte tua se volessi mettere la descrizione di una scacchiera che secondo te non puo' essere ridotta con questo algoritmo fino ad una delle configurazioni di base.

[axpgn]

"Quinzio":Sarebbe davvero gradito da parte tua se volessi mettere la descrizione di una scacchiera che secondo te non puo' essere ridotta con questo algoritmo fino ad una delle configurazioni di base.

E come potrei se neppure tu sai com'è definito l'algoritmo?

"Quinzio":
E' un algoritmo (che andrebbe ovviamente specificato meglio)

Di fatto, finora, di volta in volta, hai preso delle scacchiere, eliminato gran parte delle caselle ed infine sistemato gli ultimi tasselli; ovviamente arrivi comunque a soluzione (e non è neanche complicato) ma altrettanto ovviamente non è una dimostrazione e neppure un algoritmo (cioè una procedura ben definita che preveda tutti i casi possibili e giunga alla conclusione voluta).
IMHO

Cordialmente, Alex