Permutazioni pari

[MindFlyer]

Con riferimento a QUESTO THREAD, dimostrare i seguenti due lemmi.

Sono dati n contenitori numerati da 1 a n, ognuno dei quali contiene un oggetto. Dimostrare che:

1) ogni permutazione degli n oggetti nei contenitori può essere ottenuta componendo scambi di coppie di oggetti che si trovano in contenitori consecutivi;

2) ogni permutazione pari degli n oggetti nei contenitori può essere ottenuta componendo cicli di terne di oggetti che si trovano in contenitori consecutivi. Ad esempio, se A,B,C sono 3 oggetti in contenitori consecutivi (in quest'ordine), dopo un ciclo avranno l'ordine B,C,A.

[enomis_costa88]

Visto che nessuno lo guarda..proviamoci!

1)Passo base:
Qualsiasi permutazione di due elementi è ottenibile con l’operazione data.

Passo induttivo:
Se l’elemento uno è stato mandato in posizione i-esima applicando l’operazione data alle coppie in posizione:
(i;i-1),(i-1;i-2)…(2;1) mando l’elemento uno nella posizione 1 e ottengo una permutazione su n-1 elementi (l’elemento uno non è stato toccato e posso fingere che non esista) che è ottenibile per ipotesi induttiva.

2) Un ciclo di 3 elementi si può scomporre in due trasposizioni ed è quindi pari.

Inoltre applicando cicli di 3 elementi adiacenti posso ottenere qualsiasi ciclo di 2i+1 elementi adiacenti:
applico il ciclo di 3 adiacenti agli elementi in posizione 1,2,3; poi agli elementi in posizione: 3,4,5 e così via fino agli elementi in posizione 2i-1,2i,2i+1 ottenendo il ciclo richiesto.

Passo base:
Ogni permutazione pari di 3 elementi è ottenibile con le operazioni richieste:
le permutazioni pari sono (1,2,3); (2,3,1);(3,1,2) e sono facilmente ottenibili.

Passo induttivo:
Ipotizzo la permutazione pari abbia mandato l’elementi uno in posizione 2i+1-esima.
Allora mi basta applicare il ciclo di elementi adiacenti e di lunghezza 2i+1 per 2i volte per riportare l’elemento 1 nella posizione iniziale.

Ipotizzo l’abbia mandato in posizione 2i-esima.
Allora analogamente a prima posso mandarlo in posizione 2.
Dalla posizione due applicando il ciclo di lunghezza 3 agli elementi in posizione uno, due , tre lo mando in posizione uno.

In entrambi i casi ottengo una permutazione pari su un’insieme di n-1 elementi (l’elemento uno non è stato toccato e posso fingere che non esista) che è ottenibile per ipotesi induttiva.