Permutazioni
Vediamo chi lo risolve per primo:
Gli interi da $1$ a $2012$ sono scritti in una riga, ma in ordine sparso. La seguente operazione viene eseguita ripetutamente: se il primo numero è $k$, i primi $k$ numeri della riga vengono riscritti nell'ordine inverso a quello in cui sono.
Dimostrare che dopo un certo numero (finito) di queste operazioni il primo numero della fila sarà $1$.
Risposte
beh succedera' quando si incontra proprio il numero $1$...
E chi ti dice che potrai avere il numero uno?
Uhm forse avevo capito male il problema.
E' ovvio che per qualunque numero di numeri ci sia, prima o poi si troverà 1. Si verica empiricamente con numeri piccoli, il vero problema è dimostrarlo analiticamente.
"UmbertoM":
E' ovvio che per qualunque numero di numeri ci sia, prima o poi si troverà 1.
Perché è ovvio?
Ciao,
intendi il primo numero posizionale?
Cioè se abbiamo che in posizione $1$ c'è il numero $k$, si cercano tutti i numeri $[1,k]$ e ci "salviamo" le loro posizioni, poi si invertono tutti in-place.
PS: è una visione algoritmica della questione...
"milizia96":
se il primo numero è $k$, i primi $k$ numeri vengono riscritti nell'ordine inverso a quello in cui sono.
intendi il primo numero posizionale?
Cioè se abbiamo che in posizione $1$ c'è il numero $k$, si cercano tutti i numeri $[1,k]$ e ci "salviamo" le loro posizioni, poi si invertono tutti in-place.
PS: è una visione algoritmica della questione...
Spiego meglio: se in posizione $1$ c'è il numero $k$, tutti i numeri che compaiono nelle prime $k$ posizioni vengono riscritti al contrario, cioè:
il numero che sta in posizione $1$ finisce in posizione $k$;
il numero che sta in posizione $2$ finisce in posizione $k-1$;
il numero che sta in posizione $3$ finisce in posizione $k-2$;
...
il numero che sta in posizione $k-1$ finisce in posizione $2$;
il numero che sta in posizione $k$ finisce in posizione $1$.
(ho modificato leggermente il primo post per rendere un po' più chiara la questione...)
il numero che sta in posizione $1$ finisce in posizione $k$;
il numero che sta in posizione $2$ finisce in posizione $k-1$;
il numero che sta in posizione $3$ finisce in posizione $k-2$;
...
il numero che sta in posizione $k-1$ finisce in posizione $2$;
il numero che sta in posizione $k$ finisce in posizione $1$.
(ho modificato leggermente il primo post per rendere un po' più chiara la questione...)
[/quote]Perché è ovvio?[/quote]
Perchè si verifica empiricamente con numeri minori, ad esempio 4 5 o 6. Tuttavia dimostrarlo in via analitica non è affatto semplice.
Perchè si verifica empiricamente con numeri minori, ad esempio 4 5 o 6. Tuttavia dimostrarlo in via analitica non è affatto semplice.
comunque intuitivamente qualsiasi numero $n$ venga a trovarsi in prima posizione, con un'operazione successiva esso si troverà in $n_(ma)$ posizione. E dunque tutti i numeri prima o poi dovrebbero venire a trovarsi nella rispettiva posizione, a meno che 1 non venga a trovarsi in prima posizione prima che tutto ciò avvenga
[size=200]$A_(A_(A_(A_(A_A))))^(A^(A^(A^(A^A))))$[/size]
[size=200]$A_(A_(A_(A_(A_A))))^(A^(A^(A^(A^A))))$[/size]
Gli interi da $1$ a $2012$ sono scritti in una riga, ma in ordine sparso. La seguente operazione viene eseguita ripetutamente: se il primo numero è $k$, i primi $k$ numeri della riga vengono riscritti nell'ordine inverso a quello in cui sono.Io dimostrerei per induzione che per ogni $n in NN$ (e non solo per $n=2012$) si ha la proprietà da dimostrare.
Dimostrare che dopo un certo numero (finito) di queste operazioni il primo numero della fila sarà $1$.
Notazione: con \(*\) indico l'operazione indicata,
cioè scrivere i primi \(k\) numeri della riga nell'ordine inverso se il primo numero della riga è \(k\)
BASE: $n=1=> $ immediato
PASSO: sia $n>=1$ intero
Ipotesi induttiva: Comunque prendo una sequenza di tutti gli interi da $1$ a $n$, eseguendo \(*\) un numero finito di volte ottengo una sequenza che inizia con \(1\).
Tesi induttiva: Comunque prendo una sequenza di tutti gli interi da $1$ a $n+1$, eseguendo \(*\) un numero finito di volte ottengo una sequenza che inizia con \(1\).
Dimostrazione: Consideriamo la generica sequenza \[ \Large{ a_1^{(0)} a_2^{(0)} a_3^{(0)} \ldots a_k^{(0)} \ldots a_n^{(0)} a_{n+1}^{(0)} }\]
- [*:35dn8oxo] se \(a_1^{(0)} =1 \) ho finito.
[/*:m:35dn8oxo]
[*:35dn8oxo]se \(a_{1}^{(h)} = n+1\) per qualche \(h\) naturale, eseguendo \(*\)abbiamo una nuova sequenza dove \(a_{n+1}^{(h+1)} =n+1\) e continuando sarà sempre \(a_{n+1}^{(k)} =n+1\) per ogni \(k \in \mathbb{N}\). Quindi verranno modificati solo i primi \( n\) termini della sequenza, che sono tutti numeri tra $1$ e $n$.
Per ipotesi induttiva si arriva ad una sequenza che inizia per \(1\).[/*:m:35dn8oxo]
[*:35dn8oxo]se \(a_{n+1}^{(0)} =n+1\) siamo come nel caso precedente[/*:m:35dn8oxo]
[*:35dn8oxo] altrimenti,
Sia \(m \in {1,2,3,...,n}\) tale che \(a_{n+1}^{(0)} =m \). E' immediato constatare che \(a_{n+1}^{(h)} =m \) per ogni \(h\).
Se per assurdo non si arrivasse mai ad una sequenza che inizia per $1$, allora, siccome tutte le possibili sequenze sono in numero finito, vuol dire che ci sarà un ciclo, cioè esisteranno $l_1,l_2$ tali che $a_1^{(l_1)} a_2^{(l_1)} a_3^{(l_1)} \ldots a_k^{(l_1)} \ldots a_n^{(l_1)} a_{n+1}^{(l_1)}$ sarà coincidente con $a_1^{(l_1+l_2)} a_2^{(l_1+l_2)} a_3^{(l_1+l_2)} \ldots a_k^{(l_1+l_2)} \ldots a_n^{(l_1+l_2)} a_{n+1}^{(l_1+l_2)}$.
E dato che $a_{n+1}^{(l_1)} =a_{n+1}^{(l_2)} =m$, ciò è equivalente a dire che
la sequenza $a_1^{(l_1)} a_2^{(l_1)} a_3^{(l_1)} \ldots a_k^{(l_1)} \ldots a_n^{(l_1)}$ sarà coincidente con $a_1^{(l_1+l_2)} a_2^{(l_1+l_2)} a_3^{(l_1+l_2)} \ldots a_k^{(l_1+l_2)} \ldots a_n^{(l_1+l_2)}$.
Ecco, nella sequenza $a_1^{(l_1)} a_2^{(l_1)} a_3^{(l_1)} \ldots a_k^{(l_1)} \ldots a_n^{(l_1)}$ non c'è l'elemento $m$, ma c'è l'elemento $n+1$. Se $k_1$ è l'indice tale che $a_(k_1)^(l_1) = n+1$.
Allora consideriamo questa stessa sequenza mettendo $m$ al posto di $n+1$, cioè $a_(k_1)^(l_1) =m$.
Questa sequenza ha $n$ termini e contiene tutti gli elementi da $1$ a $n$. Però c'è un problema: eseguendo \(*\) $l_2$ volte si arriva esattamente alla stessa sequenza. Quindi non si arriverà mai ad una sequenza che inizia oer $1$. Questo è in contrasto con l'ipotesi induttiva. Assurdo [/*:m:35dn8oxo][/list:u:35dn8oxo]
Io ho ragionato in maniera molto simile. Anch'io l'ho fatto per induzione, distinguendo casi simili ai tuoi. Ma secondo me nell'ultimo punto hai reso le cose più difficili di quello che erano. Io infatti me la sono cavata così:
Nel corso delle mosse il numero $n+1$ non verrà mai a trovarsi in prima posizione. In questo modo tutti gli spostamenti riguarderanno al massimo i primi $n$ interi, quindi $m$ non sarà mai spostato. Potendo trascurare $m$, ci siamo ricondotti ad una sequenza di $n$ numeri in riga, con l'unica differenza che al posto del numero $m$ troviamo il numero $n+1$, ma ciò non ha importanza perché $n+1$ non si troverà mai all'inizio e non influenzerà in alcun modo gli spostamenti.
Nel corso delle mosse il numero $n+1$ non verrà mai a trovarsi in prima posizione. In questo modo tutti gli spostamenti riguarderanno al massimo i primi $n$ interi, quindi $m$ non sarà mai spostato. Potendo trascurare $m$, ci siamo ricondotti ad una sequenza di $n$ numeri in riga, con l'unica differenza che al posto del numero $m$ troviamo il numero $n+1$, ma ciò non ha importanza perché $n+1$ non si troverà mai all'inizio e non influenzerà in alcun modo gli spostamenti.
Avevo un po' voglia di giochicchiare, perciò ho scritto un algoritmo un po' idiota per risolvere questo problemino:
es. l'algoritmo dice che con $n=200000$ ci vogliono $130308$ passi (ovvio è un'istanza).
con $n=2012$ ci vogliono $1673$ passi
si potrebbe pure calcolarne la complessità (analisi dell'algoritmo), perciò limitare superiormente il numero di passi che potrebbe eseguire. Penso sia interessante, se ho un po' di voglia lo aggiungo
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static int DIM = 10;
static int ONE = 1;
//codice per generare una permutazione di [1,DIM] elementi
void permutation(int* PER){
int tem;
int i;
char* PER_b = calloc(DIM+1,sizeof(char));
srand(time(NULL));
PER[0]=1;
i=1;
while(i<=DIM){
while(PER_b[tem = ((rand()%DIM)+1)]){
}
PER[i]=tem;
PER_b[tem]=1;
i++;
}
free(PER_b);
}
int order_inversion_swap(int* PER){
int i;
int k;
int tem;
int j = 0;
k=PER[1];
while(k!=ONE){
i=1;
while(i<k){
tem=PER[(k-i+1)];
PER[k-i+1] = PER[i];
PER[i]=tem;
i++;
}
k=PER[1];
//printf("k: %d\n",k);
j++;
}
return j;
}
int main(void){
int* PER;
int i;
scanf("%d",&DIM);
PER = malloc(sizeof(int)*DIM+1);
permutation(PER);
printf("\npassi %d\n",order_inversion_swap(PER));
free(PER);
printf("\n");
return 0;
}es. l'algoritmo dice che con $n=200000$ ci vogliono $130308$ passi (ovvio è un'istanza).
con $n=2012$ ci vogliono $1673$ passi
si potrebbe pure calcolarne la complessità (analisi dell'algoritmo), perciò limitare superiormente il numero di passi che potrebbe eseguire. Penso sia interessante, se ho un po' di voglia lo aggiungo
Mi sono perso nel finale della dimostrazione di Gi8. Forse la mia idea segue la stessa linea.
Essendo le permutazioni finite, per $ n$ sufficientemente grande, dopo $n$ passi avremo necessariamente incontrato $2$ permutazioni identiche. Sia $m$ passi la distanza tra loro. Partendo da qualsiasi permutazione compresa tra le due identiche, dopo $ m$ passi devo trovare la stessa permutazione. Sia $p$ il massimo numero in posizione $1$ tra le permutazioni incontrate durante questi $m$ passi. Questo numero verra' spostato in posizione $p$-esima al passo successivo rispetto a quello in cui si trova in posizione $1$. Dato che tutti i numeri in posizione $1$ sono $
Marmi
Essendo le permutazioni finite, per $ n$ sufficientemente grande, dopo $n$ passi avremo necessariamente incontrato $2$ permutazioni identiche. Sia $m$ passi la distanza tra loro. Partendo da qualsiasi permutazione compresa tra le due identiche, dopo $ m$ passi devo trovare la stessa permutazione. Sia $p$ il massimo numero in posizione $1$ tra le permutazioni incontrate durante questi $m$ passi. Questo numero verra' spostato in posizione $p$-esima al passo successivo rispetto a quello in cui si trova in posizione $1$. Dato che tutti i numeri in posizione $1$ sono $
Marmi
Anche la tua dimostrazione è interessante (anche se non ho capito quel "per n sufficientemente grande" all'inizio).
Vi metto un'ulteriore dimostrazione (non di mia elaborazione però):
Associamo ad ogni sequenza un numero intero $k$, ottenuto nel seguente modo:
- si individuano tutti i numeri $m$ che sono nella corretta posizione (ad esempio il 3, se è nella terza posizione).
- $k$ si ottiene facendo $k= sum 2^m $
Si osserva che, eseguendo una mossa, il numero $k$ può solo crescere (o al limite rimanere invariato, ma ciò solo se il primo numero della riga è uguale a 1).
Questo avviene poiché, se in posizione $1$ si trova il numero $m$, la mossa porterà $m$ nella giusta posizione (quindi $k$ incrementa di $2^m$). I numeri che occupano posizioni maggiori di $m$ rimangono lì dove sono (non influiscono sull'incremento/decremento di $k$). Supponendo che i numeri che si trovano in posizioni comprese tra $2$ e $m-1$(compresi) fossero tutti ordinati prima della mossa, e vengano disordinati dopo la mossa, si ha al massimo un decremento di $k$ uguale a $2^m-4$ unità. Quindi $k$ subisce come minimo un incremento uguale a $4$.
Ma $k$ non può assumere valori arbitrariamente grandi, quindi si giungerà necessariamente ad una situazione "stabile" in cui $k$ non subirà più nessun incremento: questa situazione è proprio quella dell'$1$ come numero iniziale.
Vi metto un'ulteriore dimostrazione (non di mia elaborazione però):
Associamo ad ogni sequenza un numero intero $k$, ottenuto nel seguente modo:
- si individuano tutti i numeri $m$ che sono nella corretta posizione (ad esempio il 3, se è nella terza posizione).
- $k$ si ottiene facendo $k= sum 2^m $
Si osserva che, eseguendo una mossa, il numero $k$ può solo crescere (o al limite rimanere invariato, ma ciò solo se il primo numero della riga è uguale a 1).
Questo avviene poiché, se in posizione $1$ si trova il numero $m$, la mossa porterà $m$ nella giusta posizione (quindi $k$ incrementa di $2^m$). I numeri che occupano posizioni maggiori di $m$ rimangono lì dove sono (non influiscono sull'incremento/decremento di $k$). Supponendo che i numeri che si trovano in posizioni comprese tra $2$ e $m-1$(compresi) fossero tutti ordinati prima della mossa, e vengano disordinati dopo la mossa, si ha al massimo un decremento di $k$ uguale a $2^m-4$ unità. Quindi $k$ subisce come minimo un incremento uguale a $4$.
Ma $k$ non può assumere valori arbitrariamente grandi, quindi si giungerà necessariamente ad una situazione "stabile" in cui $k$ non subirà più nessun incremento: questa situazione è proprio quella dell'$1$ come numero iniziale.
Ciao,
Intendevo questo: essendo le permutazioni finite, iterando l'operazione descritta ad un certo punto dovrò ritrovare una permutazione già incontrata.
Bella la dimostrazione.
Bello anche il problema: da dove nasce?
Ciao,
Marmi
Intendevo questo: essendo le permutazioni finite, iterando l'operazione descritta ad un certo punto dovrò ritrovare una permutazione già incontrata.
Bella la dimostrazione.
Bello anche il problema: da dove nasce?
Ciao,
Marmi
Il problema postato è del Preimo di quest'anno.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo