Permutazioni di $\{1,\ldots,4k\}$

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,4k\}$

Messaggio da jordan » 21 ago 2016, 23:00

Own. (a) Dato un intero positivo $n$ multiplo di $8$, sia $\sigma$ una permutazione di $\{1,\ldots,n\}$. Dimostrare che esistono $1\le i<j\le n$ tali che $n$ divide $i^{\sigma(i)}-j^{\sigma(j)}$.

(b) Dato un intero positivo $n$ multiplo di $4$, sia $\sigma$ una permutazione di $\{1,\ldots,n\}$. Dimostrare che esistono $1\le i<j\le n$ tali che $n$ divide $i^{\sigma(i)}-j^{\sigma(j)}$.

[Caso $n=2016$ qui]
Ultima modifica di jordan il 22 ago 2016, 00:24, modificato 3 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,8k\}$

Messaggio da polarized » 21 ago 2016, 23:40

$n$ può essere multiplo di 16? Perché sono riuscito a dimostrarlo per $k$ dispari e con $k$ pari ho qualche problemino
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,8k\}$

Messaggio da jordan » 21 ago 2016, 23:45

$n$ è un qualunque multiplo di $8$ (quindi anche di $16$, se $k$ è pari). Comunque, il caso $k$ dispari sarebbe già "metà" del problema :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,8k\}$

Messaggio da polarized » 21 ago 2016, 23:58

Sì hai ragione, l'ho fatto senza scrivere carta e penna e mi sono accorto solo ora che il problema che avevo si risolve
Testo nascosto:
Sulla falsariga di quanto fatto prima
Considero i numeri $2k, 2^2k, 2^3k$; se almeno 1 dei primi 2 viene mandato in numeri $\ge 3$ allora la differenza tra quello e il terzo sarà divisibile per $8k$ (perdonatemi per il pessimo uso della lingua italiana)

Mi resta da considerare il caso in cui $2k$ viene mandato in $2$ e $2^2k$ in $1$.

Sottocaso 1: $k$ dispari.
Valuto ora la loro differenza dei due precedenti termini

$$ 4k^2-4k=4k(k-1)=8k\dfrac{k-1}{2}$$

Che è quindi un multiplo di $8k$

Sottocaso 2: $k$ pari.
Scrivo $k=2h$. Ciò significa che $4k^2=4k\cdot 2h=8kh$ che anche stavolta è multiplo di $8k$
Volendo (credo) si può generalizzare anche per tutti gli $n$ nella forma $n=(pq)^tk$ con $t\ge 2$
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:

Nuovo punto (b)

Messaggio da jordan » 22 ago 2016, 00:21

Molto bene anche qui (e decisamente piu' facili della mia). Ho aggiunto un punto (b) per evitare di creare un nuovo thread
The only goal of science is the honor of the human spirit.

Rispondi