TorreDomino

[ghira]

Ho sentito questo non tanto tempo fa. Qualcuno sa da dove viene?

Come qualsiasi persona normale, prendo una scacchiera n x n, ci metto n torri (degli scacchi) in modo che nessuno attacchi un'altra, e riempio le caselle rimaste coi domino. Per quali n posso fare tutto ciò?

[axpgn]

Per

Testo nascosto, fai click qui per vederlo

$n=8$

si può fare … e si può fare anche per

Testo nascosto, fai click qui per vederlo

$n=4$

… forse ho trovato uno schema per

Testo nascosto, fai click qui per vederlo

$n$ pari

Cordialmente, Alex

[axpgn]

Aggiungo che

Testo nascosto, fai click qui per vederlo

è sempre possibile per $n$ multipli di $4$; adesso devo capire se sono gli unici .

Cordialmente, Alex

[axpgn]

Oltre a ciò

Testo nascosto, fai click qui per vederlo

anche per $n$ che sia uno più di un multiplo di quattro

[ghira]

Le cose sembrano complicarsi un po' per gli altri casi. La mia soluzione oltre questo punto non è assurdamente complicata ma mi sto chiedendo se ci sono metodi più semplici.

[orsoulx]

Testo nascosto, fai click qui per vederlo

La tassellatura è possibile solo per $ n=4k vv n=4k+1 " " (con " " k in NN) $, per dimostrarlo basta osservare che la scacchiera di lato $ 4 $ è tassellabile: poniamo le torri lungo una delle diagonali, scambiamo di colonna (o di riga) le due torri centrali e ricopriamo con tessere del domino le caselle libere (dopo aver sistemato una tessera, la posizione delle restanti è obbligata).
Una scacchiera con lato multiplo di $ 4 $ si può suddividere in quadrati $ 4 x 4 $ che si toccano con un vertice lungo una diagonale, tassellabili con la tecnica precedente, e in rettangoli, privi di torri, il cui lati sono tutti multipli di $ 4 $.
Ognuna delle scacchiere precedente si può orlare con una riga è una colonna, nell'intersezione delle due linee si pone la torre mancante e si tassellano i due rettangoli liberi di lati $ 1 $ e un multiplo di $ 4 $.
Per dimostrare che le scacchiere di lato $ n=4k+2 vv n=4k+3 $ non sono tassellabili basta un controllo di parità: numerando le colonne e le righe da $ 1 $ a $ n $, le possibili posizioni delle torri sono una permutazione di $ 1, 2, ... , n $ dove i numeri rappresentano la colonna occupata dalla torre della i-esima riga; tutte le torri della permutazione identica occupano caselle del medesimo colore, diciamo nere; ogni altra permutazione si può ottenere da questa con un certo numero di scambi ed ogni scambio o lascia invariato il numero di torri che occupano una casella bianca o lo varia di $ 2 $.
Le tessere del domino coprono sempre una casella nera ed una bianca, necessitano quindi di un numero uguale di caselle dei due colori libere e questo, nei due casi, comporta invece un numero dispari di torri su caselle bianche.

Ciao

[ghira]

Questo è più breve e pulito del mio metodo. Grazie.

[axpgn]

Beh, è orsoulx

@orsoulx

Testo nascosto, fai click qui per vederlo

Grazie per avermi evitato di spiegare come sono giunto alla parte "positiva" della soluzione , mentre per la parte "negativa" avrei dovuto usare una scacchiera vera .
Non ho capito bene l'ultimissima frase ovvero "comporta invece un numero dispari di torri su caselle bianche" quindi me la sono spiegata così …

Se $n=4k+2$ con $k in NN$, le caselle sono $n^2=(4k+2)^2=16k^2+16k+4$, perciò le caselle nere sono $8k^2+8k+2$ e altrettante caselle bianche.
Posizionando le torri sulla diagonale, le caselle libere di un colore diventano $8k^2+4k$ quindi la differenza di caselle dei due colori è $4k+2$ (ovvio )
Ora, siccome abbiamo detto (notare come mi sono appropriato della tua soluzione ) che ad ogni scambio di torri (per passare da una permutazione all'altra) avremo due caselle libere in più di colore e due in meno dell'altro (oppure nessuna variazione), la differenza tra i due colori varia sempre di $4$ (o non varia affatto) ma dato che $4k+2$ non è multiplo di quattro la differenza non si azzera mai e quindi non è possibile coprire le caselle libere con le tessere del domino.
Un fatto simile accade con $n=4k+3$.
Va bene?

Cordialmente, Alex

[orsoulx]

@Alex:

Testo nascosto, fai click qui per vederlo

non esattamente: la tua è un'altra dimostrazione che opera sulla totalità delle caselle libere, mentre la mia sulla loro metà (l'ispirazione è un classico dei giocherelloni matematici: "da una scacchiera quadrata si eliminano due caselle poste in angoli opposti, dimostrare che la parte restante non può essere ricoperta con tessere del domino").
Condizione necessaria per il ricoprimento è l'uguaglianza fra il numero di caselle nere e quello delle bianche.
Nel nostro caso il numero di caselle non occupate dalle torri vale, nei due casi:
$ (4n+2)^2-(4n+2)=16n^2 +12n+2 $;
$ (4n+3)^2-(4n+3)=16n^2 +20n+6 $.
La metà di questi è un numero dispari, mentre inizialmente (con tutte le torri sul medesimo colore) è pari e ogni scambio di posizione di due torri, producendo una variazione di $ 0 $ o $ +-2 $, non modifica la parità.

Ciao

[axpgn]

Ah, ok, adesso ho capito da dove proveniva quel "dispari" che non avevo compreso
Grazie.

Cordialmente, Alex