Gioco delle N lampadine tutte spente (come fare?)

Ciao a tutti.
Ho cercato qualcosa di attinente alle lampadine sul forum ma ciò che ho trovato (le mille rane, le n lampadine in cerchio, le 100 lampadine, ecc.) non mi hanno fornito alcuno spunto alla soluzione del mio problema.

Ho N lampadine accese/spente a caso. Ho N interruttori con ciascun interruttore che cambia lo stato di M lampadine predefinite contemporaneamente. Trovare la sequenza del minimo numero di interruttori da premere in modo che tutte le lampadine si spengano.

Facciamo un esempio con N=6:
Sia lo stato iniziale (1=accesa e 0=spenta) delle 6 lampadine (da 1 a 6 da sx verso dx):
1 0 1 0 1 1

Di seguito il comportamento dei 6 interruttori:
1: 1 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 1 e 6)
2: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
3: 3 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3 e 5)
4: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)
5: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
6: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)

Ora ragionandoci un pochino è lampante che per spegnere tutte le lampadine basta premere gli interruttori 1 e 3 perchè:
stato iniziale:
1 0 1 0 1 1
premendo l'interruttore 1 si cambia lo stato delle lampadine 1 e 6 e si passa a:
0 0 1 0 1 0
premendo l'interruttore 3 si cambia lo stato delle lampadine 3 e 5 e si passa a:
0 0 0 0 0 0
portando le lampadine ad essere tutte spente

Ma se abbiamo N lampadine con N interruttori che commutano M lampadine generate casualmente come posso impostare la ricerca della soluzione con un algoritmo?

Voi come impostereste la ricerca della soluzione a questo problema?

Grazie,
Giovanni.

Dove hai trovato questo "gioco" ?

ps: IMHO è un problema di informatica, non un gioco: se fosse così, fallo spostare nella stanza di INFORMATICA, che trovi in ALTRE DISCIPLINE, e mostra i tuoi tentativi di soluzione.

Un indizio: XOR.

Ultima modifica di veciorik il 14/09/2019, 22:07, modificato 1 volta in totale.

@gimasci99
Conosci un po' di algebra lineare?

Dove hai trovato questo gioco ?

E' un classico anche all'interno dei puzzlegames.

Dove hai trovato questo "gioco" ?

ps: IMHO è un problema di informatica, non un gioco: se fosse così, fallo spostare nella stanza di INFORMATICA, che trovi in ALTRE DISCIPLINE, e mostra i tuoi tentativi di soluzione.

Ciao veciorik.
Sono nuovo del forum e se il moderatore ritiene opportuno spostarlo nella sezione informatica per me va benissimo. Infatti in pricipio io stesso ero indeciso se inserire tale domanda in questa sezione o nella sezione informatica. Poi ho scelto questa perchè mi è stato proposto come gioco da un amico a cui non ho chiesto dove l'abbia trovato.
Dopodichè hai ragione, la soluzione passerà da un'implementazione informatica. Quindi rimetto la decisione sul posto più appropriato al moderatore.

Un indizio: XOR.

So bene cos'è un XOR ma potresti essere un tantino più specifico sull'eventuale soluzione che ti è venuta in mente?

Grazie,
Giovanni.

@gimasci99
Conosci un po' di algebra lineare?

Ciao Bokonon.
Sì la conosco bene. Tu come la applicheresti al problema?
Grazie,
Giovanni.

Dove hai trovato questo gioco ?

E' un classico anche all'interno dei puzzlegames.

Sono d'accordo con te. Oggi anche i più classici dei giochi (anche solo di logica pura) passano per implementazioni informatiche nel momento in cui li si va a generalizzare. Come dicevo a veciorik io stesso ero indeciso se postarla qui o nella sezione informatica. Ad ogni modo lascio al moderatore la decisione.

Grazie in anticipo per eventuali suggerimenti per impostarne la soluzione.

Qualcosa non mi quadra nell'impostazione del quesito. Se il sistema è dato, nessuno mi assicura che la combinazione di comandi sia compatibile con il raggiungimento di una soluzione.
Ad esempio, ci potrebbe essere una lampadina (accesa) non collegata ad alcun interruttore, o due lampadine (con stato iniziale opposto) comandate da un unico interruttore, o altre combinazioni parimenti impossibili.
A meno che il quesito non sia proprio "come collegheresti interruttori a lampadine per minimizzare i comandi necessari a spegnerle tutte, qualunque sia il loro stato iniziale?"

Io suggerirei all'OP di postare per intero ed esattamente il testo del problema originale; così com'è scritto anche a me sembra un po' vago … IMHO

Cordialmente, Alex

Comunque, a naso, dal punto di vista informatico, visto che le N lampadine forniscono N informazioni elementari, saranno necessari almeno N interruttori (ovvero la possibilità di modificare il sistema in almeno N modi diversi) cui corrispondono fino ad N operazioni per garantire in ogni caso lo spegnimento.
Aumentando il numero di interruttori potrà diminuire il numero massimo di operazioni necessarie, fino a diventare una sola, se gli interruttori sono in numero pari (e corrispondono) a tutte le combinazioni acceso/spento possibili (2^n).
...A meno di voler contare sulla possibilità di fulminare le lampadine accendendole e spegnendole per migliaia di cicli, in tal caso basta un interruttore generale e stare per settimane a lavorarci.