OliForum Matematico

Si ha una scacchiera 5x5, e alcune celle sono `accese', mentre le altre sono `spente'. Una mossa consiste nell'`invertire' (da accese diventano spente, da spente diventano accese) 5 celle, a forma di croce (cosi`: http://www.log24.com/log/pix03A/031005-Cross.gif, senza le celle azzurre). Lo scopo del gioco e` spegnere tutte le celle. E` sempre possibile vincere questo gioco, indipendentemente dalla configurazione iniziale? E` possibile generalizzare a scacchiere di forma e dimensione diverse, e con `maschere' diverse (invece che a croce)?

Io e un mio amico abbiamo trovato una dimostrazione al caso piu` generale (non si specifica forma, dimensione, etc etc), pero` molto probabilmente e` sbagliata xD
Buon lavoro!

Avendo io perso forse un po' troppo tempo in questo http://www.ciunga.it/xgames/paintz/ gioco ti posso assicurare che no, non è possibile. Il mio metodo risolutivo del gioco dovrebbe funzionare anche come dimostrazione dell'impossibilità, appena trovo tempo di formalizzare il tutto provo a spiegarlo.

Ah, btw, è impossibile che la dimostrazione sia giusta per scacchiere diverse. Mentre 5x5 non funziona, se prendi una 8x8 ho un metodo risolutivo che funziona sempre (la 8x8 è il secondo livello del mio link).

Un brainstorming con Giulio mi ha portato alla conferma delle mie supposizioni, la dimostrazione e` fallace xD

eheh abbiamo mappato tutto il caso particolare del 5x5
Se potesse interessare, ci sono esattamente 4 gruppi distinti di configurazioni (cioè uno non è raggiungibile da un altro) e solo uno di questi gruppi è risolvibile, e cioè ovviamente quello che contiene la configurazione con tutte le luci spente.

Io penso di aver sbagliato qualcosa nell'intendere il problema... ma per qualunque scacchiera NxN è sicuramente impossibile se le caselle negli angoli sono spente... quelle non possono essere cambiate a quanto ho capito :|

in una versione puoi anche cambiare solo 4 o 3 caselle se stai sul bordo o nell'angolo