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!
E` sempre possibile vincere?
E` sempre possibile vincere?
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
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).
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
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
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.
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.
