Un reticolo 5 x 5 senza ReMo privato della sua ultima colonna deve diventare un reticolo 5 x 4 altrettanto ReMo-free. Partendo, allora, da uno qualsiasi di questi ultimi (sono tutti equivalenti) si può provare a colorare un'ulteriore colonna senza creare un ReMo: operazione impossibile.
Partendo, ad esempio da quello privato della prima riga (l'ultimo nel disegno precedente), notiamo che la prima e quarta riga sono complementari, così come la seconda e la terza, solo l'ultima è speciale: era nel 6 x 4 complementare della prima che è stata tolta.
Una coppia di righe complementari non crea alcun problema: possiamo aggiungere in quinta posizione il simbolo che preferiamo e non nasce alcun ReMo. Al contrario, due righe che non lo siano hanno sempre due coincidenze di simboli: in una posizione appare O in entrambe, in un'altra X. L'unico modo per impedire la formazione di un ReMo è scrivere in quinta colonna due simboli diversi: O in una e X nell'altra.
Pertanto le sole colorazioni della quinta colonna che non producono ReMo nelle prime 4 righe sono le due indicate in figure, purtroppo, qualunque sia il simbolo posto nella posizione Q, nasceranno due ReMo aventi in Q un vertice in comune.
O X O X . . O . . X . | . O . . O . . X . . X
X O O X . . X . . O . | . X . . X . . O . . O
O X X O . . X . . O . | . X . . X . . O . . O
X O X O . . O . . X . | . O . . O . . X . . X
X X O O . .
Q . .
Q . | . O . . X . . O . . X
Abbiamo quattro colorazioni diverse di un 5 x 5 (le 4 colonne di partenze giustapposte ad una delle 4 disegnate dopo la barra verticale) che comportano due ReMo, le restanti $2^5-4=28$ ne presentano almeno tre. Le colonne con 4 o 5 simboli uguali si scartano immediatamente, ne restano 16 con tre simboli di un tipo e due dell'altro: se non siete convinti, basta provare!
Dunque un reticolo 5 x 5 presenta sempre almeno due ReMo. Notando che, nel caso ne presentasse uno solo, cancellando la colonna cui appartiene un lato del medesimo si otterrebbe comunque un 5 x 4 ReMo-free, mi ero convinto che quelli trovati fossero gli unici possibili e che pertanto i due ReMo dovessero presentare sempre un vertice in comune.
Bella cantonata che ha portato alla correzione di un mio precedente intervento [a proposito! Qualcuno sa dirmi come si può ottenere il carattere barrato? Ho provato con i tag <strike> </strike> dell'HTML, ma non funziona].
Dimostrare che le quattro colorazioni trovate sono equivalenti alla fig. 1, che riporto è poco più di un gioco. Possiamo fare una gara a chi ci riesce in meno mosse.
- reticolo2.png (11.57 KiB) Visto 22412 volte
Resta da esaminare il caso di due ReMo coni lati appartenenti a linee tutte diverse, se così non fosse, cancellando la linea in comune si ricadrebbe, magari dopo una lecita rotazione di 90°, nel caso precedente .
Cacellando le due colonne su cui si trovano i lati dei due ReMo (una per ciascuno) residua un 5 x 3 ReMo-free. Questa volta, tanto per non annoiarci, partiamo da quello mancante della quarta riga. Restano due colonne da colorare, 32^2=1024 maniere possibili, tantine per essere affrontate a mano, ma fortunatamente sono possibili semplificazioni.
La riga che difetta della sua complementare è adesso la terza. La prima è complementare dell'ultima e la seconda della quarta.
O O X . . . . . O . . O . . X . . X
O X O . . . . . X . . X . . O . . O
X O O . . . . . X . . X . . X . . X
X O X . . . . . O . . X . . O . . O
X X O . . . . . O . . O . . O . . X
Dobbiamo colorare la quarta colonna in modo da formare
uno ed un solo ReMo.
Mettendo una O in terza riga, qualunque colorazione delle restanti quattro porterebbe a più di un ReMo (mettendo quattro X se ne trovano 3, mettendo tre X e una O un ReMo in corrispondenza della O ed almeno un altro fra le X, mettendo due o più O almeno uno in corrispondenza di ciascuna O).
Siamo costretti a mettere X e restano 16 possibilità fra cui solo le quattro indicate sul disegno sono accettabili. Ma anche per la quinta colonna abbiamo le stesse condizioni ed otteniamo le stesse possibili colorazioni.
Resta da abbinare la quarta colonna con la quinta, due colonne uguali sono da escludere e lo scambio dei posti è ininfluente, quindi sei sole possibilità quattro delle quali non sono accettabili.
La prima può essere abbinata solo con l'ultima: negli altri due casi nasce fra le due un ReMo di troppo. La seconda solo con la terza: nell'altro caso i due ReMo avrebbero un vertice in comune nella terza riga. La terza non può essere abbinata con la quarta, perché si forma fra loro un ReMo in seconda e quarta riga, Due sole soluzioni: quelle disegnate sotto.
O O X O X . . . . . O O X O X
O X O X O . . . . . O X O X O
X O O X X . . . . . X O O X X
X O X O O . . . . . X O X X O
X X O O X . . . . . X X O O O
Che sono equivalenti, molto 'vicine': differiscono solo per lo scambio degli elementi in posizione 4,4 e 5,5. Eppure, stranamente, servono ben quattro passaggi elementari per trasformarne una nell'altra: lo scambio delle colonne 2 con 3 e 4 con 5; lo scambio delle righe 1 con 2 e 4 con 5.