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
si ma sigma(3) è 2 passi più avanti di sigma(1)
cioè nella formula c'è scritto che $sigma(i) != sigma(i+1)$ ma non c'è scritto che $sigma(i) != sigma(i+2)$..
cioè nella formula c'è scritto che $sigma(i) != sigma(i+1)$ ma non c'è scritto che $sigma(i) != sigma(i+2)$..
"TomSawyer":
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".
"perché ogni $\sigma$ assume un valore diverso nell'intervallo $[1,n]$, perciò tutti i valori di quell'intervallo sono "coperti""
quindi da come ho inteso questa frase, non ci possono essere ripetizioni di numeri se si hanno n $sigma$ altrimenti alcuni valori dell'intervallo resterebbero scoperti... nn trovi?
aaah ma penso che tomsawyer si riferisse al fatto che $sigma(i) != sigma(i+1)$ perchè $sigma(i) = n in [1,i]$ mentre $sigma(i+1) = k in [1, i+1]$ e quindi c'è un passo in più rispetto a prima
quindi $sigma(3) = {1,2,3}$ mentre $sigma(4) = {1,2,3,4}$
tieni conto che questa qui è solo una mia interpretazione, potrei aver detto qualche scemenza..
quindi $sigma(3) = {1,2,3}$ mentre $sigma(4) = {1,2,3,4}$
tieni conto che questa qui è solo una mia interpretazione, potrei aver detto qualche scemenza..
"Mega-X":
aaah ma penso che tomsawyer si riferisse al fatto che $sigma(i) != sigma(i+1)$ perchè $sigma(i) = n in [1,i]$ mentre $sigma(i+1) = k in [1, i+1]$ e quindi c'è un passo in più rispetto a prima
quindi $sigma(3) = {1,2,3}$ mentre $sigma(4) = {1,2,3,4}$
tieni conto che questa qui è solo una mia interpretazione, potrei aver detto qualche scemenza..
boh forse son io che avevo inteso male...
io direi che c'è solo una cosa da fare... aspettare conferme o meno da tomsawyer in persona...
anche se guardando così a occhio e croce..mi piace di più la tua dimostrazione
ciò non esclude che possano essere entrambe giuste, però vediamo cosa dice l'autore del post a proposito della frase 
già..
Mi sa che a forza di spiegare cosa intendo per $\sigma$ mi sono espresso male . Quando dico che $\sigma \in S_n$ è una permutazione dei primi $n$ interi positivi, intendo che $\sigma(1)$ può essere uguale a un numero qualsiasi dell'intervallo $[1,n]$. Quindi se $\sigma(1)=n$, per esempio, nessuno tra $\sigma(2),\ldots,sigma(n)$ è uguale a $n$, ma agli altri valori rimasti di quell'intervallo, permutandolo. Spero di essere stato definitivamente chiaro. Quindi le vostre soluzioni sono sbagliate.
Hint: per dimostrare che non possono formare una progressione geometrica, si consideri che $a_(n-1)=a_0p^(n-1)/q^(n-1)$, con $p>q\ge1$ l'ipotetica ragione e $a_i$ sono i termini della sequenza.
. Quando dico che $\sigma \in S_n$ è una permutazione dei primi $n$ interi positivi, intendo che $\sigma(1)$ può essere uguale a un numero qualsiasi dell'intervallo $[1,n]$. Quindi se $\sigma(1)=n$, per esempio, nessuno tra $\sigma(2),\ldots,sigma(n)$ è uguale a $n$, ma agli altri valori rimasti di quell'intervallo, permutandolo. Spero di essere stato definitivamente chiaro. Quindi le vostre soluzioni sono sbagliate.Hint: per dimostrare che non possono formare una progressione geometrica, si consideri che $a_(n-1)=a_0p^(n-1)/q^(n-1)$, con $p>q\ge1$ l'ipotetica ragione e $a_i$ sono i termini della sequenza.
aaaaahhh ora ho capito finalmente... tutti prendono valori a caso ma diversi tra loro ehehe
quindi volendo se l'intervallo è [1,5] si può avere che
$sigma(1)=5,sigma(2)=2,sigma(3)=4,sigma(4)=1,sigma(5)=3$
finalemnte è chiaro
quindi volendo se l'intervallo è [1,5] si può avere che
$sigma(1)=5,sigma(2)=2,sigma(3)=4,sigma(4)=1,sigma(5)=3$
finalemnte è chiaro
da qui si deduce che se $sigma(1)$ ha n combinazioni possibili, $sigma(2)$ ne ha n-1 e via dicendo finchè $sigma(n)$ ha solo una combinazione, che è l'ultimo valore rimasto, giusto?
allora sappiamo che in una progressione aritmetica la differenza è costante,
quindi quindi ipotizzando per assurdo possiamo dire che $nsigma(n)-(n-1)sigma(n-1)=(n-1)sigma(n-1)-(n-2)sigma(n-2)=...=2sigma(2)-sigma(1)$
dividendo tutto per il membro di destra possiamo dire che
$(nsigma(n)-(n-1)sigma(n-1))/(2sigma(2)-sigma(1))=((n-1)sigma(n-1)-(n-2)sigma(n-2))/(2sigma(2)-sigma(1))=...=1$
quindi $(nsigma(n)-(n-1)sigma(n-1))equiv0mod(2sigma(2)-sigma(1))
e anche $((n-1)sigma(n-1)-(n-2)sigma(n-2))equiv0mod(2sigma(2)-sigma(1))
ipotizziamo che la differenza $(2sigma(2)-sigma(1))$ dia un numero pari e ipotizziamo che entrambi i numeri $sigma(2)$ e $sigma(1)$ siano pari.
allora nell'intervallo [1,n] riamarranno liberi due numeri dispari, la loro differenza allora sarà data da un numero pari meno un numero dispari o viceversa (è il valore assoluto tanto da considerare) in quanto i coefficienti n, n-1,n-2 ecc sono una volta nueri pari e una volta numeri dispari.
quindi un numero pari meno un numero dispari da un numero dispari.
sarebbe quindi che un numero dispari deve essere divisibile per uno pari, il che è assurdo.. quindi la tesi iniziale è da negare e quindi è verificato che nn si può costituire una progressione aritmetica.
questa volta va bene , o quasi bene, vero?
se non va bene.. beh ci dormo su.. sento che nn son completamente fuori starda nel caso sia errata o no?
quindi quindi ipotizzando per assurdo possiamo dire che $nsigma(n)-(n-1)sigma(n-1)=(n-1)sigma(n-1)-(n-2)sigma(n-2)=...=2sigma(2)-sigma(1)$
dividendo tutto per il membro di destra possiamo dire che
$(nsigma(n)-(n-1)sigma(n-1))/(2sigma(2)-sigma(1))=((n-1)sigma(n-1)-(n-2)sigma(n-2))/(2sigma(2)-sigma(1))=...=1$
quindi $(nsigma(n)-(n-1)sigma(n-1))equiv0mod(2sigma(2)-sigma(1))
e anche $((n-1)sigma(n-1)-(n-2)sigma(n-2))equiv0mod(2sigma(2)-sigma(1))
ipotizziamo che la differenza $(2sigma(2)-sigma(1))$ dia un numero pari e ipotizziamo che entrambi i numeri $sigma(2)$ e $sigma(1)$ siano pari.
allora nell'intervallo [1,n] riamarranno liberi due numeri dispari, la loro differenza allora sarà data da un numero pari meno un numero dispari o viceversa (è il valore assoluto tanto da considerare) in quanto i coefficienti n, n-1,n-2 ecc sono una volta nueri pari e una volta numeri dispari.
quindi un numero pari meno un numero dispari da un numero dispari.
sarebbe quindi che un numero dispari deve essere divisibile per uno pari, il che è assurdo.. quindi la tesi iniziale è da negare e quindi è verificato che nn si può costituire una progressione aritmetica.
questa volta va bene , o quasi bene, vero?
se non va bene.. beh ci dormo su.. sento che nn son completamente fuori starda nel caso sia errata o no?
Non ho capito molto della tua formulazione. Prova a riscrivere più rigorosamente quelle considerazioni sui numeri pari/dispari, perché ora non riesco a seguire il filo.
allora sappiamo che in una progressione aritmetica la differenza è costante,
quindi quindi ipotizzando per assurdo possiamo dire che $nsigma(n)-(n-1)sigma(n-1)=(n-1)sigma(n-1)-(n-2)sigma(n-2)=...=2sigma(2)-sigma(1)$
dividendo tutto per il membro di destra possiamo dire che
$(nsigma(n)-(n-1)sigma(n-1))/(2sigma(2)-sigma(1))=((n-1)sigma(n-1)-(n-2)sigma(n-2))/(2sigma(2)-sigma(1))=...=1$
quindi $(nsigma(n)-(n-1)sigma(n-1))equiv0mod(2sigma(2)-sigma(1))
e anche $((n-1)sigma(n-1)-(n-2)sigma(n-2))equiv0mod(2sigma(2)-sigma(1))
ipotizziamo che la differenza $(2sigma(2)-sigma(1))$ dia un numero pari e ipotizziamo che entrambi i numeri $sigma(2)$ e $sigma(1)$ siano pari (per completezza diciamo che l'intervallo è comporto da $n>=4$ elementi, per il caso limite con tre elemnti è facile verificare direttamente)
allora nell'intervallo [1,n] rimarranno, dopo aver fatto tutte le combinazioni, due numeri dispari, in quanto due numeri pari son già stati "usati".
notiamo che i coefficienti1,2,3,...,n sono uno pari e uno dispari, quindi quando si fa la differenza tra un fattore e il suo predecessore, un coefficiente è pari e l'altro è dispari, quindi avendo due numeri dispari, uno dei due coefficienti è pari e l'altro è dispari, quindi ci sarà una differenza tra un numero pari e un numero dispari che da un numero dispari, ok?
quindi il rapporto descritto sopra deve essere tra un numro pari e unnumero dispari e non deve dare resto, il che è assurdo.. e quindi segue la tesi..
scritto meglio ora? lo purtroppo esprimermi non è il mio forte...
quindi quindi ipotizzando per assurdo possiamo dire che $nsigma(n)-(n-1)sigma(n-1)=(n-1)sigma(n-1)-(n-2)sigma(n-2)=...=2sigma(2)-sigma(1)$
dividendo tutto per il membro di destra possiamo dire che
$(nsigma(n)-(n-1)sigma(n-1))/(2sigma(2)-sigma(1))=((n-1)sigma(n-1)-(n-2)sigma(n-2))/(2sigma(2)-sigma(1))=...=1$
quindi $(nsigma(n)-(n-1)sigma(n-1))equiv0mod(2sigma(2)-sigma(1))
e anche $((n-1)sigma(n-1)-(n-2)sigma(n-2))equiv0mod(2sigma(2)-sigma(1))
ipotizziamo che la differenza $(2sigma(2)-sigma(1))$ dia un numero pari e ipotizziamo che entrambi i numeri $sigma(2)$ e $sigma(1)$ siano pari (per completezza diciamo che l'intervallo è comporto da $n>=4$ elementi, per il caso limite con tre elemnti è facile verificare direttamente)
allora nell'intervallo [1,n] rimarranno, dopo aver fatto tutte le combinazioni, due numeri dispari, in quanto due numeri pari son già stati "usati".
notiamo che i coefficienti1,2,3,...,n sono uno pari e uno dispari, quindi quando si fa la differenza tra un fattore e il suo predecessore, un coefficiente è pari e l'altro è dispari, quindi avendo due numeri dispari, uno dei due coefficienti è pari e l'altro è dispari, quindi ci sarà una differenza tra un numero pari e un numero dispari che da un numero dispari, ok?
quindi il rapporto descritto sopra deve essere tra un numro pari e unnumero dispari e non deve dare resto, il che è assurdo.. e quindi segue la tesi..
scritto meglio ora? lo purtroppo esprimermi non è il mio forte...
Non va bene, perché tu basi la tua conclusione sull'ipotesi che $\sigma(1)$ e $\sigma(2)$ siano pari. Poi si capisce poco anche perché "rimarranno due numeri dispari", che tu decidi che siano consecutivi nella sequenza.
Non penso che questa strada porti da qualche parte.
Non penso che questa strada porti da qualche parte.
"TomSawyer":
Non va bene, perché tu basi la tua conclusione sull'ipotesi che $\sigma(1)$ e $\sigma(2)$ siano pari. Poi si capisce poco anche perché "rimarranno due numeri dispari", che tu decidi che siano consecutivi nella sequenza.
Non penso che questa strada porti da qualche parte.
no nn decido che siano consecutivi, possono essere anche 1 e 99 però sono due numeri dispariche rimangono... non concordi su questo fatto?...
ps è così sbagliato ipotizzare che $\sigma(1)$ e $\sigma(2)$ siano pari per ipotesi?...
allora cercherò altre vie
OK forse ci sono arrivato.. (speriamo..)
girando sempre sul fatto che una progressione si dice aritmetica sse $a_(n+1) - a_n = c$ dove $c$ è costante
e sull'altro fatto che una progressione si dice geometrica sse $a_(n+1)/a_n = k$ dove $k$ è costante
allora scrivendo nei termini di questo problema abbiamo che
$(i+1)sigma(i+1) - isigma(i) = c$ (1)
e
$((i+1)sigma(i+1))/(isigma(i)) = k$ (2)
con $i in [1,n-1]$
nella (1) dividiamo tutto per $isigma(i)$ e abbiamo $((i+1)sigma(i+1))/(isigma(i)) - 1 = c/(isigma(i))$
tenendo conto della (2) abbiamo che $k-1 = c/(isigma(i))$
siccome $c,k in NN$ allora significa che $c$ deve essere divisibile $AAisigma(i) in NN$ praticamente per tutti i numeri
l'unico numero che è divisibile (ragionando nei naturali) per qualunque altro numero (tranne che per lo $0$) è lo $0$
quindi significa che $c$ deve essere $0$ per far si che $k$ sia un numero naturale (tanto $isigma(i)$ non assumerà mai il valore $0$ perché $i in [1, n-1]$ e $sigma(i) in [1, n]$)
se $c = 0$ allora $k-1 = 0$ e quindi $k = 1, AAi in [1,n-1]$
ciò significa che $(i+1)sigma(i+1) = isigma(i), AAi in [1,n-1]$ (3)
dividiamo ogni membro della (3) per $sigma(i+1)$ e per $sigma(i)$ ed abbiamo che
$(i+1)/(sigma(i)) = i/(sigma(i+1))$ (4)
però 2 frazioni $a/b, c/d$ sono uguali sse ${(a=c),(b=d):}$
quindi la (4) diventa ${(i+1=i),(sigma(i)=sigma(i+1)):}$
che è ovviamente assurdo $square$
(speriamo..)girando sempre sul fatto che una progressione si dice aritmetica sse $a_(n+1) - a_n = c$ dove $c$ è costante
e sull'altro fatto che una progressione si dice geometrica sse $a_(n+1)/a_n = k$ dove $k$ è costante
allora scrivendo nei termini di questo problema abbiamo che
$(i+1)sigma(i+1) - isigma(i) = c$ (1)
e
$((i+1)sigma(i+1))/(isigma(i)) = k$ (2)
con $i in [1,n-1]$
nella (1) dividiamo tutto per $isigma(i)$ e abbiamo $((i+1)sigma(i+1))/(isigma(i)) - 1 = c/(isigma(i))$
tenendo conto della (2) abbiamo che $k-1 = c/(isigma(i))$
siccome $c,k in NN$ allora significa che $c$ deve essere divisibile $AAisigma(i) in NN$ praticamente per tutti i numeri
l'unico numero che è divisibile (ragionando nei naturali) per qualunque altro numero (tranne che per lo $0$) è lo $0$
quindi significa che $c$ deve essere $0$ per far si che $k$ sia un numero naturale (tanto $isigma(i)$ non assumerà mai il valore $0$ perché $i in [1, n-1]$ e $sigma(i) in [1, n]$)
se $c = 0$ allora $k-1 = 0$ e quindi $k = 1, AAi in [1,n-1]$
ciò significa che $(i+1)sigma(i+1) = isigma(i), AAi in [1,n-1]$ (3)
dividiamo ogni membro della (3) per $sigma(i+1)$ e per $sigma(i)$ ed abbiamo che
$(i+1)/(sigma(i)) = i/(sigma(i+1))$ (4)
però 2 frazioni $a/b, c/d$ sono uguali sse ${(a=c),(b=d):}$
quindi la (4) diventa ${(i+1=i),(sigma(i)=sigma(i+1)):}$
che è ovviamente assurdo $square$
Userei meno quel $\square$ . Tu non puoi dimostrare che non possono formare una progressione aritmetica, supponendo per assurdo che formino una geometrica. I due problemi vanno trattati separatamente. Se volete, vi posto una delle due soluzioni.
. Tu non puoi dimostrare che non possono formare una progressione aritmetica, supponendo per assurdo che formino una geometrica. I due problemi vanno trattati separatamente. Se volete, vi posto una delle due soluzioni.
beh almeno ci ho provato..
cmq tom serve conoscere teoria dei numeri per dimostrare questa cosa o che?
cmq tom serve conoscere teoria dei numeri per dimostrare questa cosa o che?
"TomSawyer":
Userei meno quel $\square$
no asp dai altre 24 ore.. poi posta una delle due soluzioni:-D
voglio provarci ancora un attimo ehehe
provo un altra volta a dimostrare anche se a dire il vero mi sento molto sicuro di questa dimostrazione.. però stavolta non lo metto il $square$ per scaramanzia
$(i+1)sigma(i+1) - isigma(i) = c, AAi in [1,n-1]$ questa è l'uguaglianza che prova che la progressione considerata è una progressione aritmetica
ora dividiamo tutto per $c$ e portiamo $isigma(i)$ al secondo membro ed abbiamo:
$((i+1)sigma(i+1))/c =(isigma(i))/c + 1$, effettuiamo la somma al secondo membro ed abbiamo $((i+1)sigma(i+1))/c =(isigma(i)+c)/c$
però 2 frazioni $a/b,c/d$ sono uguali sse $a = c ^^^ b = d$ (1)
i denominatori sono uguali, infatti $c = c$
mentre per i numeratori abbiamo $(i+1)sigma(i+1) = isigma(i)+c$ (2)
dividiamo ambo i membri della (2) sia per $sigma(i+1)$ che per $sigma(i)$ ed abbiamo che
$(i+1)/(sigma(i)) = (i+c)/(sigma(i+1))$
per la (1) deve accadere che $i+1 = i+c$ e $sigma(i) = sigma(i+1)$, però la seconda è assurda e quindi è assurdo che la progressione considerata è una progressione aritmetica
procediamo ora per quella geometrica
$((i+1)sigma(i+1))/(isigma(i)) = k, AAi in [1,n-1]$ questa è l'uguaglianza che prova che suddetta progressione è una progressione geometrica
dividiamo e moltiplichiamo i 2 membri rispettivamente per $sigma(i+1)$ e per $i$ ed abbiamo
$(i+1)/(sigma(i)) = (ki)/(sigma(i+1))$ e ricordando la (1) deve accadere che $i+1 = ki$ e che $sigma(i) = sigma(i+1)$ la cui ultima uguaglianza è assurda
quindi risulta dimostrato che la progressione $isigma(i)$ non è né geometrica e né aritmetica
speriamo che è giusta..
$(i+1)sigma(i+1) - isigma(i) = c, AAi in [1,n-1]$ questa è l'uguaglianza che prova che la progressione considerata è una progressione aritmetica
ora dividiamo tutto per $c$ e portiamo $isigma(i)$ al secondo membro ed abbiamo:
$((i+1)sigma(i+1))/c =(isigma(i))/c + 1$, effettuiamo la somma al secondo membro ed abbiamo $((i+1)sigma(i+1))/c =(isigma(i)+c)/c$
però 2 frazioni $a/b,c/d$ sono uguali sse $a = c ^^^ b = d$ (1)
i denominatori sono uguali, infatti $c = c$
mentre per i numeratori abbiamo $(i+1)sigma(i+1) = isigma(i)+c$ (2)
dividiamo ambo i membri della (2) sia per $sigma(i+1)$ che per $sigma(i)$ ed abbiamo che
$(i+1)/(sigma(i)) = (i+c)/(sigma(i+1))$
per la (1) deve accadere che $i+1 = i+c$ e $sigma(i) = sigma(i+1)$, però la seconda è assurda e quindi è assurdo che la progressione considerata è una progressione aritmetica
procediamo ora per quella geometrica
$((i+1)sigma(i+1))/(isigma(i)) = k, AAi in [1,n-1]$ questa è l'uguaglianza che prova che suddetta progressione è una progressione geometrica
dividiamo e moltiplichiamo i 2 membri rispettivamente per $sigma(i+1)$ e per $i$ ed abbiamo
$(i+1)/(sigma(i)) = (ki)/(sigma(i+1))$ e ricordando la (1) deve accadere che $i+1 = ki$ e che $sigma(i) = sigma(i+1)$ la cui ultima uguaglianza è assurda
quindi risulta dimostrato che la progressione $isigma(i)$ non è né geometrica e né aritmetica
speriamo che è giusta..
Guarda, dovresti controllare un po' meglio i passaggi 
. A parte che hai scritto 10 righe, per poi tornare all'inizio del problema, non puoi decidere che non può essere una progressione aritmetica semplicemente perché $\sigma(i+1)\ne\sigma(i)$, cosa che tu fai esplicitamente.
. A parte che hai scritto 10 righe, per poi tornare all'inizio del problema, non puoi decidere che non può essere una progressione aritmetica semplicemente perché $\sigma(i+1)\ne\sigma(i)$, cosa che tu fai esplicitamente.
siccome $sigma(i+1) != sigma(i)$ come hai detto tu
e ragionando per assurdo, ponendo infatti $(i+1)sigma(i+1) - isigma(i) = c$ con $c$ costante sono pervenuto alla conclusione che $sigma(i+1) = sigma(i)$ che è assurdo
se poi ho sbagliato a fare i conti oppure non è vero che $a/b = c/d$ sse ${(a=c), (b = d):}$ beh allora ho sbagliato..
come risposta definitiva che mi dai tom?
"TomSawyer":
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.
e ragionando per assurdo, ponendo infatti $(i+1)sigma(i+1) - isigma(i) = c$ con $c$ costante sono pervenuto alla conclusione che $sigma(i+1) = sigma(i)$ che è assurdo
se poi ho sbagliato a fare i conti oppure non è vero che $a/b = c/d$ sse ${(a=c), (b = d):}$ beh allora ho sbagliato..
come risposta definitiva che mi dai tom?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo