Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: Accendi tutte le luci
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 05 Apr 2006 15:52    Oggetto: * QUIZ: Accendi tutte le luci Rispondi citando

Eugy ha suggerito un giochino in Java che ha un po' di matematica, logica e informatica alle spalle.
Il link al giochino lo trovate in questo post.

Si tratta di un quadrato 5 x 5 in cui ogni casella corrisponde a una lampadina.
Cliccando sulla casella si inverte lo stato della lampadina (se era accesa si spegne e se era spenta si accende).
Ma l'azione cambia stato anche alle lampadine contigue (in orizzontale, in verticale ma non in diagonale).

L'obiettivo è accendere tutte e 25 le lampadine.

Il quesito che pongo è:
trovare una modellizzazione matematica del problema e un algoritmo risolutivo.

E' richiesta una conoscenza di base di teoria dei gruppi e di aritmetica binaria.

A breve posterò il modello che ho sviluppato.


L'ultima modifica di ulisse il 01 Mag 2006 16:07, modificato 1 volta
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 06 Apr 2006 22:02    Oggetto: Rispondi citando

Uhm... qualcuno ci sta lavorando o la "pomposità" della domanda vi ha fatto scappare tutti?

E' molto più semplice di quel che sembra...
Soprattutto per gli informatici!

Proviamo a scomporre il problema.
Gli elementi essenziali del gioco sono 3:
1) la tavola può assumere diverse configurazioni; ci serve quindi un modo per rappresentarle. Qual è?
2) cliccando sulle caselle si cambia configurazione dunque il secondo elemento essenziale è costituito dai cambi di configurazione; ci serve quindi un modo per rappresentarli. Come si fa?
3) quando effettuo un cambio di configurazione si passa da una configurazione ad un'altra quindi è necessario individuare un modo per calcolare il risultato di un cambio di configurazione. Come si fa?

Detto in altri termini.
Se x è una configurazione e f un cambio di stato dobbiamo trovare il modo di:
1) rappresentare x
2) rappresentare f
3) calcolare f(x)

Arrivati a questo punto il modello è pronto.
Ora si tratta di studiare il modello per stabilire quali siano le sue proprietà e da esse desumere informazioni utili quali esistenza delle soluzioni, eventuale unicità, simmetrie del modello, metodi di ricerca delle soluzioni, metodi di individuazione della/e soluzioni ottimali (quelle che consentono di arrivare alla configurazione finale col minor numero di cambi di stato).
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 07 Apr 2006 00:32    Oggetto: Rispondi citando

Oh che bello!
A meno di rotazioni e trasposizioni della tavola o di permutazioni delle mosse, la soluzione (4059606) è unica e richiede 15 mosse.
Top
Profilo Invia messaggio privato HomePage
Eugy
Eroe
Eroe


Registrato: 15/01/06 01:27
Messaggi: 65

MessaggioInviato: 07 Apr 2006 23:52    Oggetto: E chi cacchio sei?? Rispondi citando

Ma sei Gauss travestito ?? Laughing Laughing
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 13 Apr 2006 23:34    Oggetto: Rispondi citando

Eccomi qua!
Pensavate fossi sparito, eh?

Invece mi ero solo assentato per produrre questa cosa qui:

Link eliminato. Trovate la nuova versione (solo gioco, niente analisi) in un post successivo)

Indovinate un po'!

Ho scritto un programmino in VBA su excel che realizza il giochino in una variante generalizzata.

Innanzi tutto un test da parte vostra sarebbe gradito.

Il codice, ovviamente, non è protetto da password ed un po' commentato ma mica tanto.

Il modello matematico sottostante è poco più che un esercizio di Algebra I che cito tanto per poter pronunciare paroloni come "spazio vettoriale", "operatore", "omomorfismo" e "nucleo".
Talmente strani che non si sa bene se sono parolacce.
Ma forse proprio per la sua semplicità ho trovato intrigante investigarne le sue proprietà ricavandone dei nuovi "pezzi" da aggiungere alla versione originale.

Il tempo di mettere insieme le idee e posto anche il modello.
Ciao


L'ultima modifica di ulisse il 01 Mag 2006 14:18, modificato 1 volta
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 13 Apr 2006 23:45    Oggetto: Rispondi citando

ulisse ha scritto:
Il modello matematico sottostante è poco più che un esercizio di Algebra I che cito tanto per poter pronunciare paroloni come "spazio vettoriale", "operatore", "omomorfismo" e "nucleo".

wow !!!
stavolta so esattamente di che parli !!!
(ovvero adesso mi scarico il file)
Top
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 13 Apr 2006 23:46    Oggetto: Re: E chi cacchio sei?? Rispondi citando

Eugy ha scritto:
Ma sei Gauss travestito ?? Laughing Laughing


Seeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee! Liar
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 14 Apr 2006 00:49    Oggetto: Rispondi citando

madvero ha scritto:
ulisse ha scritto:
Il modello matematico sottostante è poco più che un esercizio di Algebra I che cito tanto per poter pronunciare paroloni come "spazio vettoriale", "operatore", "omomorfismo" e "nucleo".

wow !!!
stavolta so esattamente di che parli !!!
(ovvero adesso mi scarico il file)


Acciderba che scheggia!
Tanto veloce a rispondere che mi sono accorto solo ora che avevi già postato prima del mio secondo messaggio! Embarassed

Capperi... ho già un interlocutore!
Top
Profilo Invia messaggio privato HomePage
ioSOLOio
Amministratore
Amministratore


Registrato: 12/09/03 18:01
Messaggi: 16342
Residenza: in un sacco di...acqua

MessaggioInviato: 14 Apr 2006 12:52    Oggetto: Rispondi citando

facciamo almeno due interlocutori... Wink
scaricato..mo' lo provo....
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 15 Apr 2006 03:15    Oggetto: Rispondi citando

ioSOLOio ha scritto:
facciamo almeno due interlocutori... Wink
scaricato..mo' lo provo....


Evvai! Evvai
Top
Profilo Invia messaggio privato HomePage
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 15 Apr 2006 09:31    Oggetto: Rispondi citando

Se prima erano in due a scaricare questo file,
adesso siamo in tre a scaricare questo file.
Se prima eravamo in tre... Whistle

Forza continuate voi!
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 01 Mag 2006 13:48    Oggetto: Rispondi citando

Beh... tre beta tester direi che è un successone ma... ehm... il vostro silenzio mi preoccupa.

Vi siete addormentati con le luci accese come capita a me quando alla sera leggo qualcosa di noioso?
Very Happy
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 01 Mag 2006 15:09    Oggetto: Rispondi citando

Ecco il giochino nella nuova versione.
Ho tolto l'analisi perché "imbrattava" il codice.
Ora ci sono solo le funzioni di gioco tutte corredate da commenti.



Come vedrete (se darete un'occhiata al codice) le routine di gioco sono praticamente tutte dedicate all'interfaccia grafica.
Mentre le vere e proprie funzioni di gioco sono mostruosamente poche e banali.


L'ultima modifica di ulisse il 01 Mag 2006 15:57, modificato 1 volta
Top
Profilo Invia messaggio privato HomePage
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 01 Mag 2006 15:12    Oggetto: Rispondi citando

Ehm!
Ci stavo ragionando su... Liar

Quando avvio l'analisi o il gioco, mi da un errore di memoria esaurita... credo sia un mio problema, ma in questo modo non posso dare un parere.

Invece quando faccio partire la ricerca delle soluzioni, excel non mi permette di aprire altri file finché non termina l'esecuzione del codice... e poiché è lunghino, non ho avuto modo di vederlo compiuto.

Ho solo provato a dare un'occhiata al codice, ma figuriamoci se ci ho capito qualcosa...

Edit: questa è la risposta al post precedente...
Top
Profilo Invia messaggio privato
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 01 Mag 2006 15:17    Oggetto: Rispondi citando

Anche col nuovo file mi da un errore di run-time: memoria esaurita!
Ma perché?!
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 01 Mag 2006 15:49    Oggetto: Rispondi citando

Ecco un tentativo di spiegazione del modello.

La tavola è composta da 25 caselle.
Numeriamole da 0 (casella in basso a destra) a 24 (casella in alto a sinistra).

Alle caselle della prima riga saranno quindi abbinati, in ordine da sinistra a destra, i numeri 24, 23, 22, 21, 20 e, a seguire, le altre righe.
In questo modo, ogni stato della tavola può essere rappresentato da una stringa binaria di lunghezza 25.
I bit della stringa indicheranno lo stato delle singole caselle. I bit sono ordinati da 0 a 24 andando da destra verso sinistra e dal basso verso l'alto.

Ad esempio allo stato 0000000000000000000000000 corrisponderà la configurazione <tutte le lampadine spente> mentre allo stato 1111111111111111111111110 corrisponderà la configurazione <tutte le lampadine accese tranne la prima in basso a destra>.

Per comodità ogni stato verrà rappresentato in notazione decimale anziché binaria.
Dunque, in sostanza, ad ogni stato della tavola corrisponderà un numero intero compreso tra 0 e 2^25 - 1 = 33554431.

L'unico modo per cambiare stato alla tavola è quello di premere uno dei 25 interruttori.
Dunque abbiamo 25 mosse elementari. Sarà estremamente utile scegliere di rappresentare anch'esse con stringhe binarie di lunghezza 25.
Alla stringa 10000000000000000000000000 (tutti i bit a 0 tranne quello in posizione 24) corrisponderà l'interruttore della lampadina 24.
Ogni stringa rappresentante una di queste 25 mosse elementari avrà un unico bit posto a 1. La sua posizione nella stringa determinerà l'indice dell'interruttore.

A chi ricorda un po' di algebra lineare dico che le mosse sono degli operatori lineari che costituiscono uno spazio vettoriale 25-dim sul campo Z_2 ovvero il campo degli scalari è l'insieme {0,1}.
Di più i 25 operatori elementari costituiscono una base di questo spazio vettoriale.
Poichè tali operatori si applicano ad un numero e restituiscono un numero essi sono i funzionali lineari dello spazio vettoriale duale costituito dalle configurazioni della tavola.

Da ciò possiamo ricavare due informazioni:
1) Sequenze di mosse possono essere rappresentate da una qualsiasi stringa binaria di lunghezza 25. I bit posti a 1 indicheranno che la sequenza di mosse prevede l'intervento sui corrispondenti interruttori. Chiamiamo altezza h di una stringa il numero di 1 che in essa compaiono. Allora l'altezza di una sequenza di mosse mi dirà da quante mosse elementari è composta la sequenza.

2) se ogni configurazione è rappresentata da un numero x e ogni mossa è rappresentata da un numero a allora il risultato dell'applicazione di una mossa A a uno stato x sarà rappresentato dal numero y = A(x) = a*x dove il segno * non indica l'ordinaria moltiplicazione ma un'operazione che ancora è da definire.

Poichè x è noto, per ricavare y non ci manca che determinare quale sia il numero a associato alla mossa A e quale sia l'operazione da adottare.
Per determinarlo basta vedere come si comporta A quando le lampadine sono tutte spente.

Cosa succede allo stato x = 0 = 0000000000000000000000000 quando interveniamo, ad esempio, sull'interruttore centrale A = 4096 = 00000000000100000000000 ?
Succede che la tavola passa dallo stato x allo stato y = 0000000100011100010000000 ovvero si accendono la lampadina centrale e le altre quattro circostanti.
E se fosse x = 33554431 = 1111111111111111111111111 ? avremmo y = 1111111011100011101111111 ovvero le stessa lampadine, anziché accendersi, si spegnerebbero.

In pratica se un bit di a è pari a 1 allora il bit di x in posizione corrispondente cambia stato (se è 0 passa a 1 o viceversa).
L'operazione binaria che realizza ciò è lo XOR.

Pertanto l'azione della mossa A (rappresentata dal numero a) sullo stato x sarà y = A(x) = a XOR x.

Ora che sappiamo come si applica un operatore (la mossa) a un vettore (lo stato della tavola), vediamo come si compongono gli operatori per costituire una sequenza di mosse.
Come sarà fatto l'operatore AB ? Sappiamo che y = A(x) e che z = B(y).
Allora z = B(A(x)) = B(a XOR x) = b XOR (a XOR x) = (b XOR a) XOR x poiché l'operazione XOR è associativa.
Dunque L'operatore AB sarà associato al numero a XOR b.

Abbiamo già qualche risultato importante:
poiché lo XOR è commutativo (ovvero a XOR = b XOR a) deduciamo subito che AB = BA ovvero il risultato di una sequenza di mosse non dipende dall'ordine secondo il quale le mosse vengono eseguite.

poiché a XOR a = 0 deduciamo che A^2 = AA= I (identità) cioè gli operatori A sono delle involuzioni (ovvero applicando due volte la stessa mossa riportiamo la tavola nella configurazione iniziale).

Le due cose insieme forniscono l'ulteriore informazione:
in una qualsiasi sequenza di mosse, ogni mossa elementare non compare mai più di una volta.
Quindi le possibili sequenze di mosse sono tante quante le possibili configurazioni della tavola cioè sono in numero di 2^25 = 33554432.

Quante di queste porteranno alla stessa configurazione? Detta in altri termini data la coppia x , y esiste ed è unico l'operatore A ovvero esiste ed è unica la sequenza A di mosse che porta x in y ovvero tale che y = A(x)?

La risposta è negativa e vediamo perché.

Chiamiamo Altezza di un operatore il numero di lampadine alle quali tale operatore cambia stato.
Ad esempio gli operatori elementari corrispondenti alle nove lampadine centrali hanno altezza 5, i dodici sul bordo hanno altezza 4 e quelli sui quattro angoli hanno altezza 3.

L'altezza di un operatore A si calcola contando gli 1 presenti nella rappresentazione binaria di a.
Le soluzioni al gioco base (arrivare allo stato <tutte lampadine sono accese> partendo da <tutte le lampadine sono spente>) sono quelle di altezza 25.

Gli operatori di altezza 0 rappresentano sequenze di operatori elementari che non producono effetto sulla tavola.

In altri termini, gli operatori di altezza 0 costituiscono il nucleo dell'omomorfismo tra lo spazio degli operatori (le mosse) e lo spazio delle configurazioni della tavola.

Se il nucleo fosse ridotto al solo operatore 0 avremmo unicità della soluzione.
Poiché in questo caso il nucleo, oltre allo 0, contiene altri 3 operatori possiamo concludere che se la soluzione esiste (ed esiste) essa non è unica ma ne ha altre 3 a corredo.
Per chiarire chiamiamo 0, a, b, c i quattro operatori del nucleo.
Se x è una soluzione allora lo sono anche:
x XOR 0 (che è x stessa)
x XOR a
x XOR b
x XOR c

Probabilmente qualche teorema consente di determinare quante siano le soluzioni e quanti gli operatori del nucleo.
Nella mia ignoranza io ho classificato tutti (più di 33 milioni!) gli operatori per altezza scoprendo che ci sono solo 4 operatori nel nucleo e solo 4 soluzioni (legate tra loro dalla precedente relazione col nucleo).

Resta da spiegare il funzionamento dell'hint (ovvero come fa il programma a calcolare le mosse mancanti) e il funzionamento del gioco generalizzato (ovvero come fa il programma a individuare la sequenza di interruttori per passare da una configurazione iniziale scelta a caso ad una finale scelta anch'essa a caso).

Ormai dovrebbe essere facile rispondere per cui, prima di imbarcarmi nella scrittura, lascio a voi la tastiera...
Sempre che vogliate cimentarvi!
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 01 Mag 2006 16:05    Oggetto: Rispondi citando

Benny ha scritto:
Anche col nuovo file mi da un errore di run-time: memoria esaurita!
Ma perché?!


Ho sostituito il file.
Prova a vedere se ora funziona.
Da quanto mi hai detto il problema era stupidissimo: avevo dimenticato di togliere la definizione di un vettore LONG da 33 milioni di campi! Embarassed

Anche se la variabile non veniva usata nel programma, la presenza della sua dichiarazione obbliga VB a riservare dello spazio in memoria per la sua eventuale allocazione.
Poiché una variabile LONG occupa 4 byte, VB presumibilmente si inchiodava nel tentativo di riservare un'area di memoria di più di 130 megabyte!!!

Chiedo venia! Embarassed Embarassed Embarassed
E grazie per il debug! Very Happy
Top
Profilo Invia messaggio privato HomePage
ioSOLOio
Amministratore
Amministratore


Registrato: 12/09/03 18:01
Messaggi: 16342
Residenza: in un sacco di...acqua

MessaggioInviato: 01 Mag 2006 16:13    Oggetto: Rispondi citando

del primo da anche a me error di runtime e fa partire il debug per il motivo credo sopra spiegato da Ulisse..

il secondo invece funziona correttamente.
Top
Profilo Invia messaggio privato
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 01 Mag 2006 17:00    Oggetto: Rispondi citando

Ok, anche a me la versione 2.0 funziona...

Grazie anche per la spiegazione, qualcosa l'ho capito! Ma da qui a riuscire a riprodurre il tutto...
Top
Profilo Invia messaggio privato
rsrdrago
Eroe
Eroe


Registrato: 04/02/06 13:44
Messaggi: 55
Residenza: Vicenza

MessaggioInviato: 03 Mag 2006 06:27    Oggetto: Rispondi

ioSOLOio ha scritto:
facciamo almeno due interlocutori... Wink
scaricato..mo' lo provo....


Scusate la mia ignoranza ma come faccio a scaricare il file?
Top
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a 1, 2  Successivo
Pagina 1 di 2

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi