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

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

per ribadire i dubbi, nell'esempio fornito se le lampadine inizialmente accese sono la 1 e la 4 non c'è soluzione, perché gli interruttori 5 e 6 sono collegati senza criterio (duplicano gli interruttori 2 e 4).
andomito
Junior Member
Junior Member
 
Messaggio: 98 di 308
Iscritto il: 07/02/2019, 15:05

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

Messaggioda veciorik » 16/09/2019, 11:59

L'OP si è dileguato 2 giorni dopo aver inserito il suo primo ed unico post, non avendo avuto quello che cercava urgentemente: un algoritmo per risolvere il suo problema.
Lo ha mascherato da gioco per scongiurare domande sui suoi tentativi di soluzione.
Naturalmente l'algoritmo può non trovare la sequenza richiesta se questa non esiste, perché gli interruttori sono generati casualmente.
Tanto per giocare:
Testo nascosto, fai click qui per vederlo
Un interruttore può essere rappresentato da una stringa di N bit, uno per lampadina. Così pure lo stato iniziale.
Gli interruttori operano in XOR sugli stati; poiché XOR è commutativo e associativo la sequenza cercata non è una sequenza ordinata ma un sottoinsieme.
L'algoritmo banale consiste nell'applicare allo stato iniziale gli interruttori prima uno alla volta, poi a due a due, poi a tre a tre, e via dicendo finché non si ottiene una stringa di bit tutti a zero.
Naturalmente l'algoritmo banale è ridondante e si può ottimizzare in vari modi, sia per ridurre il numero di operazioni che per limitare il consumo di memoria.
Ma questo oltrepassa i requisiti minimi.
"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: 438 di 1135
Iscritto il: 07/03/2014, 23:42
Località: stra(VE)

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

Messaggioda gimasci99 » 16/09/2019, 12:03

andomito ha scritto:per ribadire i dubbi, nell'esempio fornito se le lampadine inizialmente accese sono la 1 e la 4 non c'è soluzione, perché gli interruttori 5 e 6 sono collegati senza criterio (duplicano gli interruttori 2 e 4).


Ciao andomito.
La tua osservazione è corretta ma nella generazione dello stato iniziale delle lampadine e delle lampadine che vengono accese/spente da ciascun interruttore viene data certezza che la soluzione esiste ed è unica.
Quindi non ci si deve preoccupare che la soluzione esista ma solo di capire come impostare l'algoritmo che porti dallo stato iniziale a quello finale con tutti 0 accendendo o spegnendo gli interruttoti in una certa sequenza.
Grazie,
Carlo.
gimasci99
Starting Member
Starting Member
 
Messaggio: 5 di 26
Iscritto il: 13/09/2019, 14:27

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

Messaggioda gimasci99 » 16/09/2019, 12:16

veciorik ha scritto:L'OP si è dileguato 2 giorni dopo aver inserito il suo primo ed unico post, non avendo avuto quello che cercava urgentemente: un algoritmo per risolvere il suo problema.
Lo ha mascherato da gioco per scongiurare domande sui suoi tentativi di soluzione.
Naturalmente l'algoritmo può non trovare la sequenza richiesta se questa non esiste, perché gli interruttori sono generati casualmente.
Tanto per giocare:
Testo nascosto, fai click qui per vederlo
Un interruttore può essere rappresentato da una stringa di N bit, uno per lampadina. Così pure lo stato iniziale.
Gli interruttori operano in XOR sugli stati; poiché XOR è commutativo e associativo la sequenza cercata non è una sequenza ordinata ma un sottoinsieme.
L'algoritmo banale consiste nell'applicare allo stato iniziale gli interruttori prima uno alla volta, poi a due a due, poi a tre a tre, e via dicendo finché non si ottiene una stringa di bit tutti a zero.
Naturalmente l'algoritmo banale è ridondante e si può ottimizzare in vari modi, sia per ridurre il numero di operazioni che per limitare il consumo di memoria.
Ma questo oltrepassa i requisiti minimi.


Gent.mo veciorik.
Non so perchè le mie risposte non vengono pubblicate ma ho sia dato risposta a ciascuno di voi che mi ha risposto (spero che almeno questa venga pubblicata), sia continuo a seguire le vostre risposte sperando che qualcuno abbia un valido suggerimento. Per quanto riguarda l'urgenza non so invece da dove si evinca nel mio post. La soluzione a questo problema cerco di trovarla per mio diletto e non per lavoro o altro. Quindi la soluzione non è un mio problema e tantomeno è urgente. Se si è in grado e si vogliono proporre delle soluzioni come generalmente si fa nei forum è bene altrimenti grazie comunque.
Giovanni.
gimasci99
Starting Member
Starting Member
 
Messaggio: 6 di 26
Iscritto il: 13/09/2019, 14:27

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

Messaggioda Bokonon » 16/09/2019, 18:29

Il metodo più semplice ed efficace è codificare gli interruttori in una matrice nel campo Z/2.
E poi operare una riduzione con Gauss-Jordan.
Data la matrice M degli interruttori di dimensione (nxm) composta da "uni" e zeri e di rango $1<=k<=m$
a) se la matrice estesa con lo stato delle lampadine ha rango (k+1) allora non c'è soluzione.
b) se hanno il medesimo rango allora ci sarà un'unica soluzione se $k=m$ oppure soluzioni multiple se k<m.

Se dovessi programmare il tutto farei così.
1) data la matrice estesa M+, richiamo la routine per gauss-jordan.
2) se $rk(M+)>rk(M)$ allora l'output è "nessuna soluzione"
altrimenti "posta il vettore delle soluzioni"

Per la verità, volendo, si potrebbe anche decidere di scartare tutti gli interruttori che sono combinazioni lineari degli altri (trovare una base) e poi risolvere come sopra ottenendo o 1 o nessuna soluzione.
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1543 di 5942
Iscritto il: 25/05/2018, 20:22

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

Messaggioda Bokonon » 16/09/2019, 19:01

Ecco un esempio prendendo quello proposto dal OP.
$ M+=( ( 1 , 0 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 , 0 ),( 0 , 0 , 1 , 1 , 0 , 1 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 , 0 ),( 0 , 1 , 1 , 0 , 1 , 0 , 1 ),( 1 , 0 , 0 , 1 , 0 , 1 , 1 ) ) $
Dopo Gauss diventa:
$( ( 1 , 0 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 , 0 ),( 0 , 0 , 1 , 1 , 0 , 1 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 , 0 ),( 0 , 0 , 0 , 0 , 0 , 0 , 0 ),( 0 , 0 , 0 , 0 , 0 , 0 , 0 ) ) $
Da cui $rk(M+)=rk(M)$ e una soluzione minimale è data dall'ultima colonna, ovvero interruttori 1 e 3.
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1544 di 5942
Iscritto il: 25/05/2018, 20:22

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

Messaggioda gimasci99 » 16/09/2019, 19:34

Ciao e grazie a tutti.
Finalmente ho capito come rispondere ossia col pulsante "Rispondi" e non quello "Cita".
Scusate quindi la mia assenza. Non mi sono dileguato e tantomeno disinteressato altrimenti avrei evitato di postare.
Ringrazio quindi:
veciorik ha scritto:Gli interruttori operano in XOR sugli stati;...L'algoritmo banale consiste nell'applicare allo stato iniziale gli interruttori prima uno alla volta, poi a due a due, poi a tre a tre, e via dicendo finché non si ottiene una stringa di bit tutti a zero.

Tuttavia a questo approccio sugli XOR preferisco quello suggerito su Gauss-Jordan perchè per 10 lampadine magari la cosa è fattibile, per 100 o 1000 ecc. potrebbe diventare inefficiente crescendo credo esponenzialmente il numero dei tentativi da fare.
Quindi proverò prima ad implementare:
Bokonon ha scritto:Il metodo più semplice ed efficace è codificare gli interruttori in una matrice nel campo Z/2. E poi operare una riduzione con Gauss-Jordan. Data la matrice M degli interruttori di dimensione (nxm) composta da "uni" e zeri e di rango $ 1<=k<=m $

Vi tengo informati.
Grazie mille.
gimasci99
Starting Member
Starting Member
 
Messaggio: 7 di 26
Iscritto il: 13/09/2019, 14:27

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

Messaggioda veciorik » 17/09/2019, 15:33

Meraviglioso !
Non conoscevo questa tecnica per risolvere un sistema di N equazioni di primo grado in N incognite.
Come si fa per applicarlo nel caso in cui tutti i numeri sono binari e l'addizione tra monomi è sostituita da xor ?
Puoi spiegarlo in questo caso, dove bisogna premere tutti gli interruttori :

$ M+=((1,0,0,1,1,1 ),(1,1,0,1,0,1),(1,1,1,0,0,1),(0,1,1,0,1,1),(0,0,1,1,1,1)) $
"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: 439 di 1135
Iscritto il: 07/03/2014, 23:42
Località: stra(VE)

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

Messaggioda Bokonon » 17/09/2019, 16:21

@veciorik

Beh più che una tecnica è LA tecnica. L'algebra lineare serve a risolvere i sistemi lineari.
Il teorema che fra le righe ho applicato è quello di Rouchè-Capelli.
Per usare l'algebra lineare in un sistema binario, basta imporre (come ho fatto) che il campo di riferimento abbia caratteristica 2 (in questo caso Z/2).Tradotto, significa che tutti i numeri interi dispari sono congrui (=equivalenti) a 1, mentre tutti i numeri pari sono congrui a zero (sto usando usando una definizione allargata di numeri pari e dispari per includere anche i negativi).

Per esempio, vediamo come opera il PC con la matrice che hai scritto, evidenziandone due passaggi.
Usando Gauss-Jordan ma usando i numeri interi, la matrice M+ diventa la matrice triangolare superiore:

$ ( ( 1 , 0 , 0 , 1 , 1 , 1 ),( 0 , 1 , 0 , 0 , -1 , 0 ),( 0 , 0 , 1 , -1 , 0 , 0 ),( 0 , 0 , 0 , 1 , 2 , 1 ),( 0 , 0 , 0 , 0 , -3 , -1 ) ) $
che è congrua a $ ( ( 1 , 0 , 0 , 1 , 1 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 ),( 0 , 0 , 1 , 1 , 0 , 0 ),( 0 , 0 , 0 , 1 , 0 , 1 ),( 0 , 0 , 0 , 0 , 1 , 1 ) ) $

Ovviamente sia l'umano e soprattutto il PC arrivano direttamente alla seconda forma se ad ogni somma rimpiazzano sempre 0 ed 1 applicando il modulo-2. Ma fondamentalmente non è necessario, si pososno fare tutti questi calcoli e anche i successivi con i numeri interi e solo alla fine effettuare la "traduzione".

La matrice triangolare già mi dice un sacco di cose. Tutti i pivot sono diversi da zero ed essendo M una matrice 5x5, significa che le sue colonne sono una base completa: pertanto so già che non esistono stati finali che non possano essere raggiunti da una combinazione degli interruttori. Tradotto, il sistema ha sempre una e una sola soluzione.

Ora umano e PC continuano con Gauss-Jordan e usano i pivot per annullare tutto ciò che sta sopra la diagonale e ottengono la matrice (già tradotta) $ ( ( 1 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 0 , 1 ),( 0 , 0 , 1 , 0 , 0 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 ),( 0 , 0 , 0 , 0 , 1 , 1 ) ) $
L'ultima colonna è la soluzione, ovvero bisogna cliccare una volta tutti gli interruttori.
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1546 di 5942
Iscritto il: 25/05/2018, 20:22

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

Messaggioda andomito » 18/09/2019, 13:47

che nostalgia di Geometria I (mio unico 30 e lode)
e che tristezza nel constatare che mi sono dimenticato quasi tutto
andomito
Junior Member
Junior Member
 
Messaggio: 99 di 308
Iscritto il: 07/02/2019, 15:05

PrecedenteProssimo

Torna a Giochi matematici

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite