Permutazioni dimostrazione
Mi aiutereste a capire questa dimostrazione per favore?
Teorema: ogni sostituzione su $ n$ elementi si può otteere eseguendo successivamente al massimo $ (n-1) $ scambi
Dimostrazione per induzione (è evidente quando $ n =2 $, la nostra ipotesi induttiva è che è vero per $ n = n-1 $, quindi dobbiamo poi dimostrarlo nel caso di sostituzioni su $n$ elementi.
( ( 1 , 2 , ... , n ),( i1 , i2 , ... , in ) )
per $ i=1 $ la sostituzione sposterà al massimo gli $ n -1 $ elementi: 2 ,3 ,fino a n. Quindi richiederà al massimo $n-2$ scambi. (è questo che non riesco a capire: come facciamo a dire che richiede al massimo $ n-2$ scambi?)
Quindi per $ i1=1 $, che è la nostra base induttiva, è dimostrato.
Supponiamo che $ i1 $ non è uguale a $ 1 $ e $ 1 $è in $ h$ , con $ 2 <= h <= n $ ,
cioè:
( ( 1 , 2 ,... , h , ... , n ),( i1 , i2 , ... , 1 , ... , n ) )
Si può ottenere attraverso uno scambio da:
( ( 1 , 2 ,... , h , ... , n ),( 1 , i2 , ... , i1 , ... , in ) ) che è uguale alla situazione vista all'inizio, cioè richiede al massimo $ n-2 $ scambi
Quindi la seconda situazione analizzata richiede al massimo $ (n-2)+1 $ scambi = $ (n-1) $ scambi c.v.d.
Teorema: ogni sostituzione su $ n$ elementi si può otteere eseguendo successivamente al massimo $ (n-1) $ scambi
Dimostrazione per induzione (è evidente quando $ n =2 $, la nostra ipotesi induttiva è che è vero per $ n = n-1 $, quindi dobbiamo poi dimostrarlo nel caso di sostituzioni su $n$ elementi.
( ( 1 , 2 , ... , n ),( i1 , i2 , ... , in ) )
per $ i=1 $ la sostituzione sposterà al massimo gli $ n -1 $ elementi: 2 ,3 ,fino a n. Quindi richiederà al massimo $n-2$ scambi. (è questo che non riesco a capire: come facciamo a dire che richiede al massimo $ n-2$ scambi?)
Quindi per $ i1=1 $, che è la nostra base induttiva, è dimostrato.
Supponiamo che $ i1 $ non è uguale a $ 1 $ e $ 1 $è in $ h$ , con $ 2 <= h <= n $ ,
cioè:
( ( 1 , 2 ,... , h , ... , n ),( i1 , i2 , ... , 1 , ... , n ) )
Si può ottenere attraverso uno scambio da:
( ( 1 , 2 ,... , h , ... , n ),( 1 , i2 , ... , i1 , ... , in ) ) che è uguale alla situazione vista all'inizio, cioè richiede al massimo $ n-2 $ scambi
Quindi la seconda situazione analizzata richiede al massimo $ (n-2)+1 $ scambi = $ (n-1) $ scambi c.v.d.
Risposte
Sai il nome di questo teorema? Vorrei aiutarti ma non mi è ben chiaro.
Tipica situazione in cui la ricerca della precisione formale rende più oscura una dimostrazione.
La proprietà è vera per $ n=1 $: bastano $ 0 $ scambi. Se ti piace di più è vera anche con $ 2 $ elementi, dove serve al massimo uno scambio.
Supponendo che sia vera per un dato $ n $, si deve dimostrare che lo sarà anche per $ n+1 $.
Con al più uno scambio possiamo portare il primo elemento nella posizione voluta (nel caso fosse la prima lo scambio non sarebbe necessario), rimangono $ n $ elementi da sistemare che, per l'ipotesi induttiva, necessiteranno al più $ n-1 $ scambi.
Il numero massimo di scambi per sistemare $ n+1$ elementi è allora $ 1+n-1=n $.
Ciao
B.
La proprietà è vera per $ n=1 $: bastano $ 0 $ scambi. Se ti piace di più è vera anche con $ 2 $ elementi, dove serve al massimo uno scambio.
Supponendo che sia vera per un dato $ n $, si deve dimostrare che lo sarà anche per $ n+1 $.
Con al più uno scambio possiamo portare il primo elemento nella posizione voluta (nel caso fosse la prima lo scambio non sarebbe necessario), rimangono $ n $ elementi da sistemare che, per l'ipotesi induttiva, necessiteranno al più $ n-1 $ scambi.
Il numero massimo di scambi per sistemare $ n+1$ elementi è allora $ 1+n-1=n $.
Ciao
B.
( ( 1 , 2 , ... , n ),( i1 , i2 , ... , in ) )
per i=1 la sostituzione sposterà al massimo gli n−1 elementi: 2 ,3 ,fino a n. Quindi richiederà al massimo n−2 scambi. (è questo che non riesco a capire: come facciamo a dire che richiede al massimo n−2 scambi?)
non conosco il nome, se ce l'ha:(
per i=1 la sostituzione sposterà al massimo gli n−1 elementi: 2 ,3 ,fino a n. Quindi richiederà al massimo n−2 scambi. (è questo che non riesco a capire: come facciamo a dire che richiede al massimo n−2 scambi?)
non conosco il nome, se ce l'ha:(
"orsoulx":
Tipica situazione in cui la ricerca della precisione formale rende più oscura una dimostrazione.
B.
Concordo totalmente !!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo