Prima i pari, poi i dispari

[fph]

Un interessante problemino che salta fuori quando si studia la <non-elementary>trasformata discreta di Fourier</non-elementary>:

(spero di riuscire a spiegarlo bene...)
Abbiamo una lista (ordinata) di $ 2^n $ elementi. Su di essa eseguiamo la seguente operazione: suddividiamo la lista in due meta', e spostiamo nella meta' di sopra tutti gli elementi di posto pari e nella meta' di sotto tutti gli elementi di posto dispari (lasciando invariato l'ordine all'interno dei due "gruppetti"). Poi ripetiamo questa operazione separatamente sulle due sotto-liste (di $ 2^{n-1} $ elementi) che abbiamo creato, e cosi' via fino a quando non arriviamo a liste di un elemento solo.
1) Quali elementi, alla fine dell'operazione, restano nella posizione di partenza?
2) Provare che se ripetiamo questa operazione due volte la lista ritorna nell'ordine iniziale.

C'e' sotto un'"idea standard" interessante, che e' istruttivo vedere almeno una volta... vediamo chi la trova.
ciao a tutti,

[Marco]

Federico, temo non si capisca. [almeno, io non l'ho capita...] perché non fai un disegnino?

[Loth]

Io ho capito cosi':

es. n=3 e $ a_k = k $
ogni riga una trasformazione:
$ 1, 2, 3, 4, 5, 6, 7, 8 $
$ 1, 3, 5, 7, 2, 4, 6, 8 $
$ 1, 5, 2, 6, 3, 7, 4, 8 $
$ 1, 2, 3, 4, 5, 6, 7, 8 $

E' il titolo che fuorvìa

[fph]

hmm... in effetti l'ho spiegato male: dopo il primo passo, i primi $ 2^{n-1} $ elementi non "comunicano" piu' con i secondi $ 2^{n-1}, $ ma si scambiano solo tra di loro in questo modo: quelli che prima occupavano posto pari all'interno della prima sotto-lista (cioe', al primo passo, i multipli di 4) si spostano all'inizio della prima sotto-lista, e cosi' per la seconda

Provo a fare un esempio... una riga ogni step, isolando a ogni passo le "sotto-liste" con delle barre verticali:
1 2 3 4 5 6 7 8
2 4 6 8 ||| 1 3 5 7 <-- ora gli elementi separati da barre non "comunicano" piu', agisco sulle sotto-liste di 4 elementi
4 8 || 2 6 ||| 3 7 || 1 5 <-- ora agisco su liste di due elementi (cioe', scambio a 2 a 2)
8 | 4 || 6 | 2 ||| 7 | 3 || 5 | 1 <--fine trasformazione, sono arrivato a liste di un elemento

Ora, se riapplico la trasformazione succede questo:
8 4 6 2 7 3 5 1 -->
4 2 3 1 8 6 7 5 -->
2 1 4 3 6 5 8 7 -->
1 2 3 4 5 6 7 8
et voila, sono tornato alla lista iniziale. Il primo punto del problema e' dimostrare che questo succede sempre.

Ditemi se con l'esempio va meglio...
ciao,

[bh3u4m]

La posizione dell'elemento n subisce una traslazione k, l'elemento n+k subisce una traslazione -k.
La seconda trasformazione ottiene da n+k, n+k-k=n. Da n, n+k. Il tutto lo riconduce alla posizione di partenza.

[fph]

La posizione dell'elemento n subisce una traslazione k, l'elemento n+k subisce una traslazione -k.
La seconda trasformazione ottiene da n+k, n+k-k=n. Da n, n+k. Il tutto lo riconduce alla posizione di partenza.

Tutto verissimo, ma se non dimostri che le due "traslazioni" sono una l'opposto dell'altra, tutto quello che hai fatto e' riscrivere la tesi in un linguaggio un po' piu' involuto...

[info]

Boh... oggi ho aperto per la prima volta questo es... ne è uscita una sol un pò assurda... Scrivo i vari step e le premesse ma per ora senza dimostrazione rigorosa...

PREMESSE

* chiamo stringa base generale di lunghezza 2^n una sequenza ordinata (a,b,c,...) con a,b,c appartenenti a C di cardinalità (termine corretto?) 2^n... n appartiene ad No.
* chiamo stringa base normale quella particolare stringa generale tale che a=1,b=2,c=3,...
* T è la trasformazione completa, quando dico "trasformazione" invece posso riferirmi ad uno o più passaggi di T;

LEMMA 1...
se abbiamo una stringa generale di lunghezza 2^t, si considerino i primi 2^c elementi [c<t]. Si consideri inoltre un'altra stringa generale di lunchezza 2^c (a1,b1,c1,...) tale che a1=a,b1=b,c1=c,.. Applicando la trasformazione ad entrambe dopo un primo passagio la seconda stringa sarà data dall'accostamento dei primi 2^(c-1) elementi della parte sinistra della prima stringa e dei primi 2^(c-1) elementi sempre della prima stringa;

DIM: verifica diretta;

LEMMA 2...
dopo la mossa k (<n) su una stringa base normale 2^n, i primi elementi di ogni sottostringa creatasi se accostati mantenendo le posizioni relative restituiscono la stringa finale ottenuta dopo l'applicazione di T alla stringa base normale di lunghezza 2^k;

DIM: utilizzo il LEMMA 1 per seguire la "storia" dei numeri nei 2 casi;

LEMMA 3..
due numeri si trovano nella medesima sottostringa dopo k passaggi sse sono congrui modulo 2^k;

DIM: per induzione;

IL PROBLEMA VERO si basa sulla risoluzione di questi due fatti e su un procedimento induttivo:

Una volta attuata T, si riparte da zero (non fraintendete! ) con la stringa ottenuta, applicando T per la seconda volta... quando dico dopo il primo passaggio da ora in poi salvo avvisi diversi mi riferisco alla seconda applicazione;

FATTO 1: la prima metà della stringa ottenuta dopo il primo passaggio per una stringa normale originaria (per "originaria" intendo senza che la trasformazione sia mai stata applicata) di lunghezza 2^(n+1) è uguale al risultato finale di T applicata per la prima volta alla stringa base normale 2^n;

DIM: lemma 2;

FATTO 2: la seconda metà della stringa ottenuta dopo il primo passaggio (mi riferisco sempre alla seconda applicazione della trasformazione) per una stringa normale originaria di lunghezza 2^(n+1) è uguale al risultato finale di T applicata alla stringa base normale 2^n ma con ogni singolo elemento aumentato di 2^n;

DIM: lemma 2+lemma 3;

Considerati i fatti, con un procedimento induttivo (immaginando che la tesi sia vera per n) si arriva alla conclusione (in pratica si applica manualmente il primo passaggio e grazie ai 2 fatti ed alle ipotesi induttive si segue la storia futura dei singoli elementi)... meno male che non ho scritto le DIM... mi sà che ci deve essere un metodo più veloce...


----------
dimenticavo: mi scuso con il grande fph che ovviamente si aspettava una sol di 3 righe e si vede invece comparire questa marea di numeri e lettere ---------------------
aspetta, forse ora ho capito in cosa può consistere questa idea! (dopo essere uscito dalla marea di lemmi)... Si basa forse sulla simmetria sinistra-destra del problema?

[fph]

dimenticavo: mi scuso con il grande fph che ovviamente si aspettava una sol di 3 righe e si vede invece comparire questa marea di numeri e lettere ---------------------
aspetta, forse ora ho capito in cosa può consistere questa idea! (dopo essere uscito dalla marea di lemmi)... Si basa forse sulla simmetria sinistra-destra del problema?

fuochino, dice il piccolo fph...
La dimostrazione lunga mi pare che contenga le idee giuste (anche se ammetto di essermi un po' perso tra le notazioni ).
Comunque prova ad approfondire la strada "simmetria destra-sinistra"...

[dario2994]

Bon... son passati 5 anni... un bell'uppino ci sta bene... dato che la soluzione ganza ancora non è stata scritta