Gioco delle N lampadine tutte spente (come fare?)
Ciao a tutti.
Ripropongo il quesito in oggetto postato nella sezione sbagliata avendo effettivamente un interesse più informatico che orientato al gioco. Di seguito il link del post nella sezione sbagliata.
https://www.matematicamente.it/forum/viewtopic.php?f=12&t=202810
Per comodità ricopio il 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 l'algoritmo per la ricerca della soluzione a questo problema?
Grazie,
Giovanni.
Ripropongo il quesito in oggetto postato nella sezione sbagliata avendo effettivamente un interesse più informatico che orientato al gioco. Di seguito il link del post nella sezione sbagliata.
https://www.matematicamente.it/forum/viewtopic.php?f=12&t=202810
Per comodità ricopio il 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 l'algoritmo per la ricerca della soluzione a questo problema?
Grazie,
Giovanni.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo