OliForum Matematico

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)}$.

Posso chiederti cosa si intende per $i^{\sigma(i)}$ ?
$i$ elevato a quel numero in cui viene mandato $i$ dalla permutazione $\sigma$?

Si, esatto

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

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

Per $n$ primo credo si possa fare agevolmente (spoiler per l'idea) anche se resta da aggiustare qualche caso che sperabilmente non da problemi 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

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$?

polarized ha scritto:io claimo che non servano ipotesi aggiuntive

Prova con $n=7$

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?

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!)

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 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ì

polarized ha scritto:Il fatto che funzionino alcuni primi e altri no mi turba

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)