Inviato: Lun Feb 26, 2007 5:16 pm Oggetto: A question for March
Vi propongo il seguente problema, sperando che sia di discussione per il mese di Marzo e che non lo risolviate prima
Diciamo che una funzione è uno "shift" se presa una successione restituisce la medesima privata del primo elemento. Esempio:
shift(1,4,5,4,6,2,.....)=4,5,4,6,2,....
Domande:
(a) esiste una funzione che al quadrato (rispetto alla composizione, ossia shift(shift(*)) sia uno shift se la successione è a valori nei naturali?
(b) stessa domanda con la successione a valori nei reali.
(c) stessa domanda con la successione a valori in un insieme finito.
Have a good March (whatever it means) _________________ I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.
Registrato: Oct 04, 2003 Messaggi: 276 Località: Como
Inviato: Mar Feb 27, 2007 10:52 am Oggetto:
Intanto, sembra molto bello! Mi sta appassionando!!!
Adesso scrivo qualche conclusione a cui sono arrivata... Penso di avere la soluzione in un caso particolare del punto 3, cioè se la cardinalità dell'insieme è di un certo tipo...
Innanzitutto, nonostante il caso "insieme finito" sia l'ultimo e quindi probabilmente il più difficile, io sono un po' bastian contrario, quindi per semplificarmi la vita ho cominciato a pensare ai casi in cui la successione potesse ammettere solo pochi valori.
Caso banale: la successione a valori in 0... ovviamente l'identità è uno shift e al quadrato è ancora uno shift... tanto giusto quanto inutile....
Poi ho pensato ad una successione a valori in 0,1. Già si fa più interessante. Mi sono accorta (probabilmente qualcuno l'ha dimostrato, e comunque non credo sia difficile da dimostrare), che moltiplicando per due un numero binario ottengo lo stesso numero shiftato. O meglio, compare uno 0 in fondo.... Ora, io ho bisogno di shiftare, quindi faccio così: prendo la mia successione, costruisco il numero binario "con la virgola":
a = a_0 , a_1 a_2 a_3...
lo moltiplico per due (a'=2a), ottenendo il numero binario
a' = a'_0 , a'_1 a'_2 a'_3
costruisco la nuova successione assegnando ad a'_0 la cifra che ho subito prima della virgola, assgnando ad a'_1 la cifra che ho subito dopo la virgola e via di seguito tutte le altre. Così ho una funzione shift. Ma io ne voglio una che faccia lo shift se composta con se stessa. Quindi non devo passare direttamente da a ad a', ma devo farlo in due passi... Avevo detto che a'=a+a, invece ora voglio farlo in due passi: nella funzione "intermedia" devo sommare ad a una parte di a. Quindi
a'=f(a)=a+xa
dove x è da determinare, in modo che applicandola due volte io ottenga 2a, cioè:
f(f(a))=f(a)+xf(a)=a+xa+x(a+xa)
e impongo che questo sia uguale a 2a.
Risolvo per x:
x^2+2x-1=0
ottenendo x=-1\pm sqrt(2),
(dove \pm sta per "più o meno" e sqrt è la radice quadrata)
che è totalmente inutile visto che la mia successione è a valori in 0,1. Ma questo mi ha fatto venire in mente un'altra cosa:
Se la funzione fosse a valori in un insieme di cardinalità N, dove N è una particolare potenza di 2 del tipo: N=2^{q-1} dove q è un quadrato perfetto, succederebbe una cosa bella:
faccio come prima, ma stavolta per ottenere lo shift non devo moltiplicare per 2 ma per q (funziona, ho provato, non avevo voglia di dimostrarlo ma sono sicura che qualcuno l'ha già fatto). Quindi l'equazione da risolvere, a differenza di prima, è
f(f(a))=f(a)+xf(a)=a+xa+x(a+xa)=qa
(invece che =2a).
Risolvendo per x si ottiene
x=-1\pm sqrt(q)
Ma q stavolta è un quadrato perfetto, e sqrt(q)-1, moltiplicato per a in base N, dovrebbe appartenere all'insieme di partenza! Quindi questa dovrebbe essere la soluzione in un caso particolare del punto 3.
Per esempio, se la cardinalità dell'insieme è 8=2^{4-1}, metto in corrispondenza biunivoca gli el dell'insieme con {0,1,...,7} e poi calcolo a=a_0,a_1 a_2...
poi f(a)=a+2a=3a (ovviamente in base
e se non ho sbagliato tutto, dopo aver ricostruito la successione a partire dal numero a', questo dovrebbe essere la mia "radice di shift"... può essere???
Detto questo, anche se quesso fosse giusto, non ho la minima idea di come estendere la cosa al caso generale!!!
AIUTO!!!!
Adesso mi sta venendo in mente che FORSE, calcolando in base N la radice di q, anche se q non è un quadrato perfetto, potrebbe funzionare lo stesso... quindi dovrebbe poter funzionare per tutti gli insiemi che hanno una cardinalità che è una potenza di 2... boh!!!!!!!!!
_________________ Ciao!
Prometto di leggerlo con attenzione dopo pranzo... Adesso devo proprio andare, è tardissimo e la giornata è già stata abbastanza lunga...
e non è ancora finita!
A dopo. _________________ I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.
Registrato: Oct 04, 2003 Messaggi: 276 Località: Como
Inviato: Mar Feb 27, 2007 12:37 pm Oggetto:
MENO MALE CHE NON L'HAI LETTO!
C'è una serie di errori di cui mi vergogno un sacco...
ERRATA CORRIGE:
le potenze di due non c'entrano ASSOLUTAMENTE niente,
ovviamente in qualsiasi base N, prendendo un numero e moltiplicandolo per N(in base 10) o per 10(in base N) ottengo quel numero con uno 0 in più...
Quindi la frase
Citazione:
stavolta per ottenere lo shift non devo moltiplicare per 2 ma per q (funziona, ho provato, non avevo voglia di dimostrarlo ma sono sicura che qualcuno l'ha già fatto)
è una grande scemata!
Quindi il tutto dovrebbe funzionare se l'insieme di partenza ha cardinalità che è un quadrato perfetto!!!!!! _________________ Ciao!
Ok... ho capito. Spero non solo io
Comunque il risultato: "funziona nel caso finito se la cardinalità dell'insieme è un quadrato perfetto" è giusto, ma non completo. Ci sono altri casi in cui funziona.
Però già questo risultato dovrebbe permetterti, vedendo le cose da un altro punto di vista, di rispondere alle prime due domande
A quanto pare non era necessario farle in ordine, avevi ragione.
Molto brava... come sempre. _________________ I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.
Registrato: Oct 04, 2003 Messaggi: 276 Località: Como
Inviato: Mar Feb 27, 2007 6:05 pm Oggetto:
Innanzitutto, GRAZIE GRAZIE GRAZIE per non aver infierito sulle scemate che ho scritto! Vi rendete conto? Mi si è fuso il cervello... in pratica, invece di scrivere che moltiplicando per 10 (in qualsiasi base) si aggiunge uno 0 alla fine, sono riuscita a scrivere che questa "strana" cosa funziona solo se la base è una potenza di 2, ANZI, ho scritto che si aggiunge uno zero se si moltiplica per ... log_2(base)+1 ... ma come ho fatto ad inventarmi sta cosa??! Va be'...
Ora, sperando di non scrivere altre scemate, mi sembra proprio di poter dire che, anche se x (si veda il post di prima ma con l'errata corrige: x=-1\pm\sqrt{N} dove N è la base in cui lavoro, ovvero la cardinalità dell'insieme), dicevo, anche se x è irrazionale, non c'è alcun problema...
a è un numero con la virgola in base N;
f(a)=a'=a*sqrt{10}
(dove sia "10", sia la radice, sia il prodotto sono intesi in base N)
quindi a' è un numero con la virgola in base N... e le cifre con cui è scritto appartengono certamente a {0,1,...N}.
E f(f(a))=a*sqrt(10)*sqrt(10)=a*10 è ancora un numero in base N.
Ora, sembrerebbero non esserci problemi, ma in realtà un problema c'è... ed è una cosa che nel caso "base quadrato perfetto" non influiva. Ovvero, come assegno, a partire da questo numero, la nuova successione? Prima avevo detto che a'_0 era la cifra subito prima della virgola e così via, ma questa cosa non funziona. Perchè se elimino la cifra delle decine al primo semi-shift, moltiplicando ancora per sqrt(10) (inteso sempre in base N... non lo scriverò più) sbaglio, perchè stavolta non sto moltiplicando per un naturale! Quindi propongo di fare così: al momento di assegnare {a'_n}, se a'>10*sqrt(10) (tutto, ripeto, in base N) elimino la cifra delle "decine" (chiamiamola così anche se sono in base N), altrimenti tengo tutto (a'_0 sarà la prima cifra, a'_1 la seconda, ecc., indipendentemente da dove sta la virgola). NB ovviamente non ci sarà mai la cifra delle centinaia... quindi non problem.
Detto questo, mi sembra di aver risolto il caso 3 per qualsiasi cardinalità... anche se dal post di lpcr non mi era sembrato di capire che si potesse fare per ogni N. E' giusto tutto quello che ho scritto? Se no, dove sta l'errore? _________________ Ciao!
Registrato: Oct 04, 2003 Messaggi: 276 Località: Como
Inviato: Mer Feb 28, 2007 9:31 am Oggetto:
Ok ok, prima che me lo diciate voi, ho sbagliato di nuovo! Il ragionamento non funziona... dicendo che toglievo la cifra delle "decine" solo se il numero è maggiore di 10sqrt(10) risolve il problema per alcune sequenze ma ne crea uno nuovo in altre, quindi niente. Non riesco a sistemarlo. Peccato.
Resta tutto corretto per quanto riguarda le basi quadrate... Proverò a cercare gli altri casi in cui funziona, come dice lpcr! Stavolta, però, prima di scrivere paginate di post piene di errori ci penserò un po' di più, promesso! _________________ Ciao!
Registrato: Oct 04, 2003 Messaggi: 276 Località: Como
Inviato: Gio Mar 01, 2007 4:57 pm Oggetto:
Finalmente ci siamo!!! (sarà perchè è il 1 marzo??!)
Punto 1: RISOLTO CON FUNZIONE ESPLICITATA
Punto 2: LA FUNZIONE ESISTE (assumendo la scelta ) MA NON RIUSCIAMO AD ESPLICITARLA... PER UN PELO ACCIDENTI!
Punto 3: RISOLTO PER BASI QUADRATE ma a quanto pare c'è altro.
Premessa doverosa: questo problema (il punto 2 in particolare) stanno spopolando in università... grazie a tutti quelli che hanno partecipato alla discussione sulla possibilità di costruire esplicitamente una funzione biunivoca da R in RxR! E soprattutto grazie lpcr, problema bellissimo!
Il concetto è questo...
Sia g una funzione biunivoca da N in NxN (per il punto 1) o da R in RxR (per il punto 2). Questa funzione, nel caso di N, si può esplicitare con la diagonalizzazione di Cantor (si chiama così o mi confondo?). Nel caso di R, la funzione esiste perchè R e RxR hanno la stessa cardinalità (in generale vale per qualsiasi insieme infinito, almeno credo)... se ho tempo dopo faccio qualche commento sulla possibilità o meno di esplicitarla...
Ho la mia successione: {sn}=s0 s1 s2 s3 ....
La funzione semishift tale che
semishift(semishift({sn})=shift({sn})
è fatta come segue.
Ad ogni elemento della successione {sn} associo una coppia ordinata di elementi tramite g:
(s0_a, s0_b) (s1_a, s1_b) (s2_a, s2_b) ...
Scrivo una nuova successione così:
s0_a s0_b s1_a s1_b s2_a s2_b ...
Elimino il primo termine:
s0_b s1_a s1_b s2_a s2_b ...
Riaccoppio i termini:
(s0_b, s1_a) (s1_b, s2_a) (s2_b, s3_a) ...
Applico alle coppie l'inversa di g:
{tn}=t0 t1 t2 t3 ...
Ora, la funzione semishift è quella che associa ad {sn} la nuova successione {tn}.
Se applico di nuovo il semishift cosa succede? Prendo {tn} e ad ogni elemento associo una coppia tramite g... otterrò proprio:
(s0_b, s1_a) (s1_b, s2_a) (s2_b, s3_a) ...
Disaccoppio, elimino il primo termine e riaccoppio:
(s1_a, s1_b) (s2_a, s2_b) ...
Utilizzo l'inversa di g e cosa ottengo?
shift{sn}=s1 s2 s3 .... !!!!!!!
Qualche commento sul caso di R... innanzitutto, il fatto che la funzione biunivoca da R in RxR esista ci garantisce che possiamo prenderne una per costruire il semishift? Eh, stiamo facendo uso dell'assioma della scelta! A meno che non riusciamo ad esplicitarne una... e ce l'avevamo QUASI fatta...
Si prenda un numero reale espresso in notazione decimale. Per comodità aggiungiamo a sinistra infiniti zeri. Per esempio radice di 2 diventa:
........00000001,41421356.........
numeriamo in questo modo le cifre del numero scritto sopra:
........87654321,12345678.........
Ora ad un numero reale associamo i seguenti due numeri reali: il primo è quello che contiene solo le cifre di posto pari (la virgola resta dov'era):
........0 0 0 0 , 1 2 3 6.......
il secondo è quello che contiene solo le cifre di posto dispari:
........ 0 0 0 1,4 4 1 5 .......
Questa cosa sembrerebbe iniettiva e suriettiva... c'è solo un piccolo piccolo problema... NON E' VERO! C'è una stupidatina che rompe le scatole! (Quale? ) Abbiamo provato ad aggirare la cosa in tutti i modi, ma non riusciamo ad uscirne... Ma è possibile esplicitare una funzione di questo tipo?
Facendo una media tra le i vari post, e considerando che è il 2 Marzo, posso dire brava
Per la funzione esplicita da R n R^2 biunvoca... sinceramente non ci ho mai pensato ad esplicitarla, ma adesso lo farò sicuramente!
Piccola chiosa... Anche il caso con basi quadrate discende direttamente da quello per il caso infinito
Adesso manca la parte più "difficile"... Le altre cardinalità per insiemi finiti.
Suggerimentino... Cosa fanno uno shift e un mezzo shift quando si incontrano? _________________ I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.
Ok... credo di avere una risposta per la bigezione "esplicita" di R^2 in R.
Come altri prima di me, anche io marchio il territorio
Tempo di controllare che funzioni e di scriverla. _________________ I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.
Allora... se la costruisco da (0,1)x(0,1) in (0,1) si offende qualcuno?
I hope no.
- Step 1: Costruiamo una funzione iniettiva da (0,1) in (0,1)x(0,1)
Ok, questa è facile:
f(x)= (x,0)
- Step 2: Costruiamo una funzione iniettiva da (0,1)x(0,1) in (0,1)
Già più difficile.
Dunque, poichè (x,y) sta in (0,1)x(0,1), allora x e y stanno in (0,1) (mi applaudo da solo per la banalità).
Allora posso scegliere una rappresentazione decimale di x e di y (senza usare l'assioma della scelta, dato che nel perggiore dei casi ce ne due, quella con il 9 periodico e quella con lo 0 periodico. Scelgo sempre quella con lo 0 periodico).
A questo punto ho:
x = 0, x1 x2 x3 x4 ....
y = 0, y1 y2 y3 y4 ....
Mando la coppia (x,y) in 0,x1 y1 x2 y2 x3 y3 ..... Chiamo g questa funzione.
Questa è iniettiva.
- Step 3: Rimontare il tutto per ottenere una funzione one to one
Suggerimento per me stesso... Usare Bernstein:
Dunque:
Chi sono gli elementi di R che non stanno nell'immagine di g?
Direi che sono quelli del tipo:
0,9x9x9x... oppure 0,x9x9....
Chiamiamoli insieme A.
Bon... a questo punto che si fa? Appunto si usa Bernstein. Vi risparmio la dimostrazione, c'è pure su Wikipedia ed è facile. L'importante è che definiti:
C_0=A
C_{n+1}=gf(C_n)
C l'unione dei C_n
la funzione F definita da:
Codice:
| f(x) se x sta in C
F(x) = |
| g^-1(x) se x non sta in C
C_2 = gf(C_1) = g(A, roba di prima) =
roba del tipo:
0,9000x0009000x0009000x.... oppure 0,x0009000x0009000x0009000....
quindi C è formato dagli elementi del tipo:
0,9(somma di potenze di 2 consecutive a partire da 2^0 zeri)x(somma di potenze di 2 consecutive a partire da 2^0 zeri)9...
oppure
0,x(somma di potenze di 2 consecutive a partire da 2^0 zeri)9(somma di potenze di 2 consecutive a partire da 2^0 zeri)x...
Detto questo, mi sembra opportuno informare il gentile pubblico che potrei aver scritto una marea di vaccate e che negherò tutto appena mi verrà fornito il tasto edit... _________________ I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.
C_2 = gf(C_1) = g(A, roba di prima) =
roba del tipo:
0,9000x0009000x0009000x.... oppure 0,x0009000x0009000x0009000....
quindi C è formato dagli elementi del tipo:
0,9(somma di potenze di 2 consecutive a partire da 2^0 zeri)x(somma di potenze di 2 consecutive a partire da 2^0 zeri)9...
oppure
0,x(somma di potenze di 2 consecutive a partire da 2^0 zeri)9(somma di potenze di 2 consecutive a partire da 2^0 zeri)x...
A questo punto deve essere (così correggo anche una cavolata indipendente):
C_2 = gf(C_1) = g(A, roba di prima) =
roba del tipo:
0,9111x1119111x1119111x.... oppure 0,x1119111x1119111x1119111....
quindi C è formato dagli elementi del tipo:
0,9(somma di potenze di 2 consecutive a partire da 2^0 o nessun uno)x(somma di potenze di 2 consecutive a partire da 2^0 o nessun uno)9...
oppure
0,x(somma di potenze di 2 consecutive a partire da 2^0 o nessun uno)9(somma di potenze di 2 consecutive a partire da 2^0 o nessun 1)x...
lpcr ha scritto:
Detto questo, mi sembra opportuno informare il gentile pubblico che potrei aver scritto una marea di vaccate e che negherò tutto appena mi verrà fornito il tasto edit...
Edit... dove sei? _________________ I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.
Registrato: Oct 04, 2003 Messaggi: 276 Località: Como
Inviato: Ven Mar 02, 2007 2:45 pm Oggetto:
Allora.... ho letto! Un paio di errorini di disattenzione...(per esempio, 0 non appartiene a (0,1)... e non è vero che f(C_1) = (A, roba di prima)... volevi dire (roba di prima,0) .... questo solo per far vedere che ho letto!!! )... A parte gli scherzi, boh sembra funzionare! Cioè, ho capito ma non ho fatto i compiti, cioè non sono andata a vedere Bernstein... andrò per curiosità. Poi commenterò! Grazie! _________________ Ciao!
Tutti i fusi orari sono GMT + 1 ora Vai a pagina 1, 2Successivo
Pagina 1 di 2
Non puoi inserire nuovi Topic in questo forum Non puoi rispondere ai Topic in questo forum Non puoi modificare i tuoi messaggi in questo forum Non puoi cancellare i tuoi messaggi in questo forum Non puoi votare nei sondaggi in questo forum
giovedì 24-mag-12 09:50
Complessivo: 102997
Persone Online:
Visitatori: 
Iscritti: 172
Totale: 172
FAQ
Cerca
Gruppi utenti
Profilo
Messaggi Privati
Login
Il ragionamento non funziona... dicendo che toglievo la cifra delle "decine" solo se il numero è maggiore di 10sqrt(10) risolve il problema per alcune sequenze ma ne crea uno nuovo in altre, quindi niente. Non riesco a sistemarlo. Peccato. 
) MA NON RIUSCIAMO AD ESPLICITARLA... PER UN PELO ACCIDENTI!
e non è vero che f(C_1) = (A, roba di prima)... volevi dire (roba di prima,0) 
)... A parte gli scherzi, boh sembra funzionare! Cioè, ho capito ma non ho fatto i compiti, cioè non sono andata a vedere Bernstein... andrò per curiosità. Poi commenterò! Grazie!