Permutazioni dei primi $n$ interi
Sia $n\ge 3$ e $\sigma \in S_n$ una permutazione dei primi $n$ interi positivi. Provare che i numeri $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ non possono formare né una progressione aritmetica né una geometrica.
Risposte
stai richiedendo una dimostrazione?
"andrew":
stai richiedendo una dimostrazione?
è ovvio che ne richiede una dimostrazione..
"TomSawyer":
Sia $n\ge 3$ e $\sigma \in S_n$ una permutazione dei primi $n$ interi positivi. Provare che i numeri $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ non possono formare né una progressione aritmetica né una geometrica.
scusa l'ignoranza ma ho un problema coi simboli.. $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ il numero tra parentesi, indica il numero di elementi di ogni permuazione? cioè nella prima c'è solo il numero uno, nella seconda il numero 1,2 e via dicendo, giusto?
"TomSawyer":
Sia $n\ge 3$ e $\sigma \in S_n$ una permutazione dei primi $n$ interi positivi. Provare che i numeri $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ non possono formare né una progressione aritmetica né una geometrica.
se fosse così allora:
in una progressione aritmica rimangno costanti le differenze tra un elemnto e l'altro appartenenti alla progressione, in un a progressione geometrica invece rimane costante il raporto.
quindi $ 2\sigma(2)-sigma(1)=n\sigma(n)-(n-1)sigma(n-1)
rimane $3=n*n!-(n-1)*(n-1)
guardiamo il termine di sinistra elaboarndo viene: $n*n*(n-1)!-(n-1)*(n-1)!$=$(n-1)!(n^2-n+1)$ ed essendo che $n>2$ questo non porà mai essere uguale a tre, quindi le differenze tra i vari elementi che compongono la progressione non possono essere in progressione aritmetica.
in modo analago, analizzando l'uguaglianza data da $ (2\sigma(2))/(sigma(1))=(n\sigma(n))/((n-1)sigma(n-1))$ si dimostra che non può essere in progressione geometrica.
però son incerto di aver capito bene o no cosa è sigma, spero che sia come l'ho intuito e quindi come ho scritto nel post prima..aspetto conferme
"fu^2":
[quote="TomSawyer"]Sia $n\ge 3$ e $\sigma \in S_n$ una permutazione dei primi $n$ interi positivi. Provare che i numeri $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ non possono formare né una progressione aritmetica né una geometrica.
scusa l'ignoranza ma ho un problema coi simboli.. $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ il numero tra parentesi, indica il numero di elementi di ogni permuazione? cioè nella prima c'è solo il numero uno, nella seconda il numero 1,2 e via dicendo, giusto?[/quote]
$\sigma(n)$ è una mappa che manda $n$ in un qualsiasi elemento dell'insieme ${1,2,\ldots,n}$.
"TomSawyer":
[quote="fu^2"][quote="TomSawyer"]Sia $n\ge 3$ e $\sigma \in S_n$ una permutazione dei primi $n$ interi positivi. Provare che i numeri $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ non possono formare né una progressione aritmetica né una geometrica.
scusa l'ignoranza ma ho un problema coi simboli.. $\sigma(1), 2\sigma(2),\ldots,n\sigma(n)$ il numero tra parentesi, indica il numero di elementi di ogni permuazione? cioè nella prima c'è solo il numero uno, nella seconda il numero 1,2 e via dicendo, giusto?[/quote]
$\sigma(n)$ è una mappa che manda $n$ in un qualsiasi elemento dell'insieme ${1,2,\ldots,n}$.[/quote]
si ma quindi $\sigma(n)$ con n=1 diventa $\sigma(1)$ e l'unico elemento dell'insiem è 1, mentre $\sigma(2)$ l'elemento dell'insieme è 2, giusto?
$\sigma(1)=1$ e $\sigma(2)$ può essere o $1$ o $2$.
"TomSawyer":
$\sigma(1)=1$ e $\sigma(2)$ può essere o $1$ o $2$.
1 o 2 su che base? casualità?
Su nessuna base, non puoi decidere quale valore assume, ma devi considerare tutti i valori possibili.
"TomSawyer":
Su nessuna base, non puoi decidere quale valore assume, ma devi considerare tutti i valori possibili.
cioè? un fattoriale, una permutazione alla fine? QUINDI $sigma(2)=2*1$ che son il numero di valori possibili che ci sono gisuto?
$sigma(3)=6$ ecc.. giusto?
Non hai capito, una permutazione non è un fattoriale. Quando scrivo $\sigma(n)$ intendo un qualsiasi numero nell'intervallo $[1,n]$. Quindi, $2\sigma(2)$, per esempio, può essere uguale a $2*1$ o $2*2$, e tu devi valutare questo numero in tutti i casi.
PS: $3\sigma(3)$ può essere uguale a $3*1$, $3*2$ o $3*3$.
PS: $3\sigma(3)$ può essere uguale a $3*1$, $3*2$ o $3*3$.
"TomSawyer":
Non hai capito, una permutazione non è un fattoriale. Quando scrivo $\sigma(n)$ intendo un qualsiasi numero nell'intervallo $[1,n]$. Quindi, $2\sigma(2)$, per esempio, può essere uguale a $2*1$ o $2*2$, e tu devi valutare questo numero in tutti i casi.
PS: $3\sigma(3)$ può essere uguale a $3*1$, $3*2$ o $3*3$.
ok ora ho capito...grazie per la pazienza
il problema allor è bello tosto..
Hmm, meno di quello che sembra. Si prosegue per assurdo e ci si arriva anche con non molti passaggi.
Hint su richiesta
.
Hint su richiesta
.
Ah, sì, nel contesto del problema, essendo $\sigma$ una permutazione, tra i numeri $1sigma(1),2sigma(2),\ldots,nsigma(n)$, $\sigma (i)$, $i\in[1,n]$, non assume mai lo stesso valore.
quindi se non asumono mai lo stesso valore $nsigma(n)!=(n+1)sigma(n+1),AAiin[1,n+1]$ giusto? quindi in un caso particolare ad esempio $sigma(1)!=sigma(2)$giusto?
Sì, giusto, perché uno è multiplo di $n$, l'altro di $n+1$ e chiaramente i numeri non possono essere uguali, per la limitatezza di $\sigma(n)$.
$\sigma(1)\ne \sigma(2)\ne \ldots \ne \sigma(n)$, perché ogni $\sigma$ assume un valore diverso nell'intervallo $[1,n]$, perciò tutti i valori di quell'intervallo sono "coperti".
$\sigma(1)\ne \sigma(2)\ne \ldots \ne \sigma(n)$, perché ogni $\sigma$ assume un valore diverso nell'intervallo $[1,n]$, perciò tutti i valori di quell'intervallo sono "coperti".
allora vdiamo se va bane questa dimostrazione per la progressione eritmetica.
per assurdo ipotizziamo che effettivamente creano una progressione aritmetica (la differenza tra due elementi rimane costante), quindi $nsigma(n)-(n-1)sigma(n-1)=2sigma(2)-sigma(1)
ci sono delle considerazioni prima:
i) per ipotesi $n-1>=2$, quindi $n>=3$
ii)essendi che $nsigma(n)!=(n+1)sigma(n+1),AAiin[1,n+1]$, allora visto che $sigma(1)=1$, segue che $sigma(2)=2$, ... , $sigma(n)=n$
sostiyuendo nell'equazione di partenza otteniamo $n^2-(n-1)^2=4-1$
$n^2-n^2-1+2n=3
il risultato è
$n=2
($n=-2$ non è stato considerato in quanto stiamo lavorando in $NN$
quindi siamo arrivati ad un risultato che contraddice lipotesi i) e ciò è assurdo, quindi è dimostrato che non può formare una progressione aritmetica.
ho fatto qualche errore?
per assurdo ipotizziamo che effettivamente creano una progressione aritmetica (la differenza tra due elementi rimane costante), quindi $nsigma(n)-(n-1)sigma(n-1)=2sigma(2)-sigma(1)
ci sono delle considerazioni prima:
i) per ipotesi $n-1>=2$, quindi $n>=3$
ii)essendi che $nsigma(n)!=(n+1)sigma(n+1),AAiin[1,n+1]$, allora visto che $sigma(1)=1$, segue che $sigma(2)=2$, ... , $sigma(n)=n$
sostiyuendo nell'equazione di partenza otteniamo $n^2-(n-1)^2=4-1$
$n^2-n^2-1+2n=3
il risultato è
$n=2
($n=-2$ non è stato considerato in quanto stiamo lavorando in $NN$
quindi siamo arrivati ad un risultato che contraddice lipotesi i) e ciò è assurdo, quindi è dimostrato che non può formare una progressione aritmetica.
ho fatto qualche errore?
OK ci sono arrivato..
Come aveva detto fu^2 (e grazie a fu^2 che ho capito come procedere altrimenti non ci sarei mai arrivato, quindi condivido la dimostrazione di questo teorema con fu^2)
una progressione si dice aritmetica sse $a_(i+1) - a_i = c, AAi in NN$ con $c$ costante
mentre si dice geometrica sse $a_(i+1)/a_i = k, AAi in NN$ con $k$ costante
con l'accorgimento che $sigma(i) = i - k$ con $k in [0, i-1]$ procediamo per assurdo dimostrando che tale progressione non è né aritmetica e né tanto meno geometrica
quindi per essere una progressione aritmetica deve accadere che $(i+1)((i+1) - (k+1)) - i(i-k) = c$
semplificando abbiamo che $(1-k)(i-k) = c$ e quindi $c$ è un numero dipendente al variare di $i$ è quindi non è mai costante
mentre per essere una progressione geometrica deve accadere che $((i+1)((i+1)-(k+1)))/(i(i-k)) = k$
e semplificando abbiamo che $(i+1)/i = c$ ed anche qui $c$ dipende al variare di $i$
Quindi possiamo dire che la progressione $isigma(i)$ non può essere né geometrica e né aritmetica $square$
Come aveva detto fu^2 (e grazie a fu^2 che ho capito come procedere altrimenti non ci sarei mai arrivato, quindi condivido la dimostrazione di questo teorema con fu^2
)una progressione si dice aritmetica sse $a_(i+1) - a_i = c, AAi in NN$ con $c$ costante
mentre si dice geometrica sse $a_(i+1)/a_i = k, AAi in NN$ con $k$ costante
con l'accorgimento che $sigma(i) = i - k$ con $k in [0, i-1]$ procediamo per assurdo dimostrando che tale progressione non è né aritmetica e né tanto meno geometrica
quindi per essere una progressione aritmetica deve accadere che $(i+1)((i+1) - (k+1)) - i(i-k) = c$
semplificando abbiamo che $(1-k)(i-k) = c$ e quindi $c$ è un numero dipendente al variare di $i$ è quindi non è mai costante
mentre per essere una progressione geometrica deve accadere che $((i+1)((i+1)-(k+1)))/(i(i-k)) = k$
e semplificando abbiamo che $(i+1)/i = c$ ed anche qui $c$ dipende al variare di $i$
Quindi possiamo dire che la progressione $isigma(i)$ non può essere né geometrica e né aritmetica $square$
DOH battuto nel tempo da fu^2..
Considerazione:
è vero che $sigma(i) != sigma(i+1)$ ma può essere che $sigma(3) != sigma(2)$ perché $sigma(3) = 1$ e $sigma(2) = 2$
Considerazione:
"fu^2":
ii)essendi che $nsigma(n)!=(n+1)sigma(n+1),AAiin[1,n+1]$, allora visto che $sigma(1)=1$, segue che $sigma(2)=2$, ... , $sigma(n)=n$
è vero che $sigma(i) != sigma(i+1)$ ma può essere che $sigma(3) != sigma(2)$ perché $sigma(3) = 1$ e $sigma(2) = 2$
"Mega-X":
DOH battuto nel tempo da fu^2..
Considerazione: [quote="fu^2"]ii)essendi che $nsigma(n)!=(n+1)sigma(n+1),AAiin[1,n+1]$, allora visto che $sigma(1)=1$, segue che $sigma(2)=2$, ... , $sigma(n)=n$
è vero che $sigma(i) != sigma(i+1)$ ma può essere che $sigma(3) != sigma(2)$ perché $sigma(3) = 1$ e $sigma(2) = 2$[/quote]
no perchè se $sigma(3) = 1$ allora sarebbe uguale a $sigma(1) = 1$ per forza, quindi non si coprirebbe più tutto l'intervallo preso [1,n] nn trovi?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo