Permutazioni di $\{1,\ldots,2016\}$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Permutazioni di $\{1,\ldots,2016\}$

Messaggio da jordan » 19 ago 2016, 08:56

Own. Sia $\sigma$ una permutazione di $\{1,\ldots,2016\}$. Dimostrare che esistono $1\le i<j\le 2016$ tali che $2016$ divide $i^{\sigma(i)}-j^{\sigma(j)}$.
Ultima modifica di jordan il 21 ago 2016, 22:59, modificato 2 volte in totale.
The only goal of science is the honor of the human spirit.

polarized
Messaggi: 96
Iscritto il: 06 feb 2015, 14:06

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da polarized » 19 ago 2016, 12:17

Posso chiederti cosa si intende per $i^{\sigma(i)}$ ?
$i$ elevato a quel numero in cui viene mandato $i$ dalla permutazione $\sigma$?
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da jordan » 19 ago 2016, 14:57

Si, esatto
The only goal of science is the honor of the human spirit.

polarized
Messaggi: 96
Iscritto il: 06 feb 2015, 14:06

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da polarized » 20 ago 2016, 19:16

Allora, credo di aver trovato una soluzione ma non credo che fosse quella pensata per risolvere il problema (in teoria nella mia testa funzionava un pigeonhole su qualche insieme, che però non sono riuscito a scrivere per il fatto che o è sbagliata, o comunque non ho idea di come funzioni la struttura moltiplicativa modulo $m$ se considero interi non coprimi)

Osservazione 1: Esistono $10$ divisori di $2016$ che hanno i suoi stessi divisori primi
Infatti $2016=2^5\cdot 3^2 \cdot 7$.

Ora, a prescindere dal tipo di permutazione, almeno due di questi avranno un esponente $\ge5$ e ciò farà sì che $2016$ li divida, e in particolare divida la loro differenza
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia

Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da Rho33 » 21 ago 2016, 17:57

Ma per un $n$ generico? Servono delle ipotesi aggiuntive? La difficoltà pare diventare abbastanza elevata... Ci sto pensando da un po' e non ho ricavato quasi nulla :oops:

polarized
Messaggi: 96
Iscritto il: 06 feb 2015, 14:06

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da polarized » 21 ago 2016, 21:29

Per $n$ primo credo si possa fare agevolmente (spoiler per l'idea) anche se resta da aggiustare qualche caso che sperabilmente non da problemi
Testo nascosto:
$$ i^{p-1}-1^{\sigma (1)}$$
Servirebbe una qualche buona idea per $n$ prodotto di primi perché quando i primi cominciano ad avere esponenti alti allora funziona allo stesso modo di 2016.. io claimo che non servano ipotesi aggiuntive ma bisogna capire come si comportano gli interi non coprimi ad $n$ al variare dell'esponente, in bocca al lupo per la ricerca di una soluzione :D
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da jordan » 21 ago 2016, 23:10

polarized ha scritto:Osservazione 1: Esistono $10$ divisori di $2016$ che hanno i suoi stessi divisori primi. Infatti $2016=2^5\cdot 3^2 \cdot 7$.

Ora, a prescindere dal tipo di permutazione, almeno due di questi avranno un esponente $\ge5$ e ciò farà sì che $2016$ li divida, e in particolare divida la loro differenza
Molto bene! Propongo una generalizzazione qui

@Rho33: Per il caso $n$ generico, la risposta "quasi sempre" negativa (o meglio, fissato un qualunque $\epsilon>0$, puoi trovare un intero $n$ sufficientemente grande tali che il numero di interi in $[1,n]$ per cui la risposta è negativa è $> (1-\varepsilon)n$ per ogni $n>n_0$)

@polarized: Non ti basterebbe porre $\sigma(1)=p-1$?
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da jordan » 21 ago 2016, 23:11

polarized ha scritto:io claimo che non servano ipotesi aggiuntive
Prova con $n=7$ :arrow:
The only goal of science is the honor of the human spirit.

polarized
Messaggi: 96
Iscritto il: 06 feb 2015, 14:06

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da polarized » 21 ago 2016, 23:25

jordan ha scritto:[...]

@polarized: Non ti basterebbe porre $\sigma(1)=p-1$?
È proprio questo il caso che speravo non creasse problemi..
Evidentemente non è così, si può dimostrare?
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da jordan » 21 ago 2016, 23:30

Ammetti anche di poter mostrare che $\sigma(1) \neq p-1$. Potresti comunque porre $\sigma(p)=p-1$, no?

Riguardo la tua domanda, si, puoi trovare tutti e soli i primi che soddisfano la condizione sopra (nota che: alcuni funzionano, alcuni no!)
The only goal of science is the honor of the human spirit.

polarized
Messaggi: 96
Iscritto il: 06 feb 2015, 14:06

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da polarized » 21 ago 2016, 23:44

jordan ha scritto:Ammetti anche di poter mostrare che $\sigma(1) \neq p-1$. Potresti comunque porre $\sigma(p)=p-1$, no?

Riguardo la tua domanda, si, puoi trovare tutti e soli i primi che soddisfano la condizione sopra (nota che: alcuni funzionano, alcuni no!)
Giusto, hai ragione, anche quello sarebbe un problema
Il fatto che funzionino alcuni primi e altri no mi turba :lol: pensavo che comunque l'operazione di "elevare a una permutazione" fosse almeno in qualche caso (tipo $n$ primo) a sua volta una permutazione ma ormai credo la faccenda sia più complicata di così
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Permutazioni di $\{1,\ldots,2016\}$

Messaggio da jordan » 21 ago 2016, 23:53

polarized ha scritto:Il fatto che funzionino alcuni primi e altri no mi turba :lol:
Mettiamo che lo stesso problema di estende ad "almeno metà" dei primi, vedi qui (in realtà, "quasi tutti", inteso alla stessa maniera del "quasi sempre" sopra)
The only goal of science is the honor of the human spirit.

Rispondi