Gioco delle N lampadine tutte spente (come fare?)

Messaggioda gimasci99 » 13/09/2019, 15:07

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.
gimasci99
Starting Member
Starting Member
 
Messaggio: 1 di 26
Iscritto il: 13/09/2019, 14:27

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda veciorik » 14/09/2019, 21:33

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.
"Dietro ogni problema c'è un'opportunità" - "Nelle prove naturali non si deve ricercare l'esattezza geometrica" - "Stimo più il trovar un vero, benché di cosa leggiera, che 'l disputar lungamente delle massime questioni senza conseguir verità nissuna" (Galileo Galilei)
Avatar utente
veciorik
Senior Member
Senior Member
 
Messaggio: 437 di 1135
Iscritto il: 07/03/2014, 23:42
Località: stra(VE)

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda Bokonon » 14/09/2019, 21:47

@gimasci99
Conosci un po' di algebra lineare?
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1541 di 5942
Iscritto il: 25/05/2018, 20:22

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda Bokonon » 14/09/2019, 21:56

veciorik ha scritto:Dove hai trovato questo gioco ?

E' un classico anche all'interno dei puzzlegames.
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1542 di 5942
Iscritto il: 25/05/2018, 20:22

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda gimasci99 » 15/09/2019, 09:43

veciorik ha scritto: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.

veciorik ha scritto: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
Starting Member
Starting Member
 
Messaggio: 2 di 26
Iscritto il: 13/09/2019, 14:27

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda gimasci99 » 15/09/2019, 09:51

Bokonon ha scritto:@gimasci99
Conosci un po' di algebra lineare?


Ciao Bokonon.
Sì la conosco bene. Tu come la applicheresti al problema?
Grazie,
Giovanni.
gimasci99
Starting Member
Starting Member
 
Messaggio: 3 di 26
Iscritto il: 13/09/2019, 14:27

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda gimasci99 » 15/09/2019, 09:55

Bokonon ha scritto:
veciorik ha scritto: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.
gimasci99
Starting Member
Starting Member
 
Messaggio: 4 di 26
Iscritto il: 13/09/2019, 14:27

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda andomito » 16/09/2019, 11:12

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?"
andomito
Junior Member
Junior Member
 
Messaggio: 96 di 308
Iscritto il: 07/02/2019, 15:05

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda axpgn » 16/09/2019, 11:21

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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14089 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda andomito » 16/09/2019, 11:37

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. :-D
andomito
Junior Member
Junior Member
 
Messaggio: 97 di 308
Iscritto il: 07/02/2019, 15:05

Prossimo

Torna a Giochi matematici

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite