Un problema di teoria dei gruppi/reticoli
Ciao a tutti.
Nel mio lavoro (sono un musicista) ho un problema che sembra essere di natura matematica. Non ho idea di come risolverlo e vorrei che qualcuno mi aiutasse o quanto meno mi facesse capire dove andare a trovare la soluzione. Non sono sicuro che si tratti esattamente di un problema di teoria dei gruppi o dei reticoli, ma spero che me lo direte voi!
Dunque, vi spiego il problema già a un certo livello di astrazione. Prendiamo l'insieme di tutti i numeri di sei cifre in base binaria, cioè i 64 numeri da 000000 a 111111. Io vorrei disporli in una successione, in modo che ogni numero sia presente una sola volta (e fin qua tutto facile), ma anche in modo che il passaggio da un numero al successivo sia ogni volta diverso. Descrivo il modo di passare da un numero al successivo come l'operazione XOR del primo numero con un numero (chiamiamolo "operatore di cambiamento"), che dia come risultato il numero successivo. Io vorrei quindi che anche la successione di "operatori di cambiamento" fossero tutti i 63 numeri da 000001 a 111111 (il numero 000000 ovviamente non può essere compreso perché è la funzione di identità), più un numero qualsiasi della successione che viene ripetuto, in modo tale che da un numero qualsiasi della successione si ritorni allo stesso numero, dopo 64 passaggi applicando in ordine i 64 numeri della successione di "operatori di cambiamento". È tutto chiaro? Perché li chiamo "operatori di cambiamento"? Perché dato un numero, ad esempio 100110, indicando con un "operatore di cambiamento" quali cifre cambiano (con 1) e quali no (con 0) si passa ad un nuovo numero, ad esempio 100110 XOR 010010 = 110100. RIngrazio tutti quelli che potranno aiutarmi!!!!
Nel mio lavoro (sono un musicista) ho un problema che sembra essere di natura matematica. Non ho idea di come risolverlo e vorrei che qualcuno mi aiutasse o quanto meno mi facesse capire dove andare a trovare la soluzione. Non sono sicuro che si tratti esattamente di un problema di teoria dei gruppi o dei reticoli, ma spero che me lo direte voi!
Dunque, vi spiego il problema già a un certo livello di astrazione. Prendiamo l'insieme di tutti i numeri di sei cifre in base binaria, cioè i 64 numeri da 000000 a 111111. Io vorrei disporli in una successione, in modo che ogni numero sia presente una sola volta (e fin qua tutto facile), ma anche in modo che il passaggio da un numero al successivo sia ogni volta diverso. Descrivo il modo di passare da un numero al successivo come l'operazione XOR del primo numero con un numero (chiamiamolo "operatore di cambiamento"), che dia come risultato il numero successivo. Io vorrei quindi che anche la successione di "operatori di cambiamento" fossero tutti i 63 numeri da 000001 a 111111 (il numero 000000 ovviamente non può essere compreso perché è la funzione di identità), più un numero qualsiasi della successione che viene ripetuto, in modo tale che da un numero qualsiasi della successione si ritorni allo stesso numero, dopo 64 passaggi applicando in ordine i 64 numeri della successione di "operatori di cambiamento". È tutto chiaro? Perché li chiamo "operatori di cambiamento"? Perché dato un numero, ad esempio 100110, indicando con un "operatore di cambiamento" quali cifre cambiano (con 1) e quali no (con 0) si passa ad un nuovo numero, ad esempio 100110 XOR 010010 = 110100. RIngrazio tutti quelli che potranno aiutarmi!!!!
Risposte
Non ci ho pensato molto e non sono neanche troppo sicuro che si possa fare (nel senso che esista in effetti una successione di operatori che funziona). Ho provato a fare qualcosa di assolutamente banale tipo prendere la sequenza degli operatori e cominciare ad applicarli partendo da $000000$, ma non funziona (si riazzera dopo $000011$ fornendo solo $3$ elementi, vale a dire $000000,000001,000011$). Una cosa un po' meno banale, che pero' immagino a un certo punto abbia gli stessi problemi, e' partire dalla fine (con $3$ cifre non funziona e fornisce solo $4$ elementi).
Ho comunque il sospetto che se esiste una successione che funziona allora ce ne sono un sacco, quindi si potrebbe provare a fare un po' di prove per vedere se tirando a caso viene fuori qualcosa, oppure studiare casi piu' piccoli e vedere se si trova qualche regolarita'.
Non vedo una connessione immediata con la teoria dei gruppi. Pero' avevo letto qualcosa di qualche $2$-gruppo che giocava qualche ruolo nel gioco del Nim (che in pratica si risolve facendo un sacco di XOR).
Bellino, ci penso...
Ho comunque il sospetto che se esiste una successione che funziona allora ce ne sono un sacco, quindi si potrebbe provare a fare un po' di prove per vedere se tirando a caso viene fuori qualcosa, oppure studiare casi piu' piccoli e vedere se si trova qualche regolarita'.
Non vedo una connessione immediata con la teoria dei gruppi. Pero' avevo letto qualcosa di qualche $2$-gruppo che giocava qualche ruolo nel gioco del Nim (che in pratica si risolve facendo un sacco di XOR).
Bellino, ci penso...
Intanto grazie. Naturalmente è un po' che ci provo, ma volevo soprattutto capire se può essere trovato un criterio generale per queste successioni. Ho iniziato con numeri di tre cifre, da 000 a 111 e si può trovare piuttosto facilmente una soluzione. Con 4 cifre ho fatto qualche prova alla cieca e sono ottimista sul fatto che si possano trovare. Ma vorrei evitare di andare a casaccio... potrei facilmente creare un programma che trova tutte le combinazioni, ma vorrei capire se esiste un criterio! Ad esempio, l'operazione XOR individua insiemi di 3 numeri (sottogruppi ciclici? scusate ma mi mancano le basi della teoria dei gruppi), ad esempio 001, 010 e 011 in modo che lo XOR di qualunque coppia di numeri dà come risultato il terzo. Esiste una qualche teoria che si è occupata di questo? Sembra che il criterio possa essere definito nei termini di queste terne di numeri. Mah!
Come la fai la sequenza per il caso con tre cifre?
Nel frattempo ho capito che solo se si elimina l'elemento neutro sia dalla successione originale, che da quella degli operatori la cosa funzione propriamente. Ad esempio: x(n)= 001,010,100,011,110,111,101 s(n)= 011,110,111,101,001,010,100. Dunque x(n+1) = x(n) XOR s(n). Dove n va da 1 a (2^N)-1 e N è il numero delle cifre binarie utilizzate. Nell'esempio quindi N=3.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo