Siano $ ~ a_1, a_2,\ldots,a_n $ n interi consecutivi e $ ~ \sigma: \{1,2,\ldots,n\} \rightarrow \{1,2,\ldots,n\} $ una permutazione di n elementi.
Dimostrare che esistono due interi distinti b,c tali che:
$ \displaystyle n \mid a_b a_{\sigma(b)} - a_c a_{\sigma(c)} $
Edit: dimenticavo che n è un numero primo!
Moldova TST 2007 - "prodotto" per una permutazione
Allora allora...
$ n=p $
E' noto che fra $ p $ interi consecutivi c'è un multiplo di $ p $. Se tale intero viene mandato dalla permutazione non in se stesso, la tesi è soddisfatta poichè poniamo che $ a_j $ sia tale intero e sia mandato in $ a_{\sigma(j)} $, allora si avrà che la coppia $ (j,\sigma(j)) $ verifica la tesi.
Supponiamo dunque che l'intero zero modulo $ p $ sia mandato in se stesso. Perchè non ve ne siano due uguali (sempre modulo p), gli interi della forma $ a_ia_{\sigma(i)} $ devono essere tutti distinti, e quindi ognuno di essi deve essere congruo ad un valore compreso fra 1 e p-1 modulo p. Quindi moltiplicando tutti questi interi avremo
$ $\prod_{i} a_ia_{\sigma(i)}\equiv (p-1)! \pmod p $
$ $ \left( \prod_{i} a_i\right)^2=(p-1)! \pmod p $
$ $ ( (p-1)! )^2\equiv (p-1)! \pmod p $
dividendo per (p-1)! che è primo con p
$ $ (p-1)!\equiv 1 \pmod p $
assurdo per il Teorema di Wilson
Al solito se qualcosa non è chiaro, chiedete!
$ n=p $
E' noto che fra $ p $ interi consecutivi c'è un multiplo di $ p $. Se tale intero viene mandato dalla permutazione non in se stesso, la tesi è soddisfatta poichè poniamo che $ a_j $ sia tale intero e sia mandato in $ a_{\sigma(j)} $, allora si avrà che la coppia $ (j,\sigma(j)) $ verifica la tesi.
Supponiamo dunque che l'intero zero modulo $ p $ sia mandato in se stesso. Perchè non ve ne siano due uguali (sempre modulo p), gli interi della forma $ a_ia_{\sigma(i)} $ devono essere tutti distinti, e quindi ognuno di essi deve essere congruo ad un valore compreso fra 1 e p-1 modulo p. Quindi moltiplicando tutti questi interi avremo
$ $\prod_{i} a_ia_{\sigma(i)}\equiv (p-1)! \pmod p $
$ $ \left( \prod_{i} a_i\right)^2=(p-1)! \pmod p $
$ $ ( (p-1)! )^2\equiv (p-1)! \pmod p $
dividendo per (p-1)! che è primo con p
$ $ (p-1)!\equiv 1 \pmod p $
assurdo per il Teorema di Wilson
Al solito se qualcosa non è chiaro, chiedete!
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Re: Moldova TST 2007 - "prodotto" per una permutaz
Ha ragione simo: stai sempre a fare tesi debolucceedriv ha scritto:Edit: dimenticavo che n è un numero primo!
Piuttosto sarebbe interessante dimostrare che funziona per qualsiasi n diverso da 2 (non necessariamente primo)...
"Sei la Barbara della situazione!" (Tap)
Eh hai ragione... è proprio debole. Anzi non è neanche tanto difficile vedere che funziona per ogni n:
- innanzitutto osserviamo che andranno moltiplicati tra loro solo numeri a,b tali che (a,n) = (b,n). Altrimenti, dopo la moltiplicazione, otteniamo troppi numeri il cui minimo comune multiplo con n è abbastanza alto, e per il pigeonhole ce ne sono due uguali.
- n deve essere libero da quadrati. Se $ ~ p^2 \mid n $, per il ragionamento di prima, se ho a tale che p || a, devo moltiplicarlo con un b tale che p || b, ma allora p^2 || ab e ci sono troppi elementi tali che $ ~ p^2 \mid (x,n) $.
- allora $ ~ n = p_1p_2 \cdots p_k $. Per lo stesso motivo di prima, i numeri tali che $ ~ (x,n) = p_1p_2\cdots p_{k-1} $ li devo moltiplicare tra loro. Ma qua entra in gioco il caso dimostrato da Boll... notate che il loro prodotto è congruo a -1 modulo $ ~ p_k $.
Ma la tesi è ancora deboluccia, caro piever.
A chi generalizza il problema ai gruppi abeliani, va in premio un abelian grape:
- innanzitutto osserviamo che andranno moltiplicati tra loro solo numeri a,b tali che (a,n) = (b,n). Altrimenti, dopo la moltiplicazione, otteniamo troppi numeri il cui minimo comune multiplo con n è abbastanza alto, e per il pigeonhole ce ne sono due uguali.
- n deve essere libero da quadrati. Se $ ~ p^2 \mid n $, per il ragionamento di prima, se ho a tale che p || a, devo moltiplicarlo con un b tale che p || b, ma allora p^2 || ab e ci sono troppi elementi tali che $ ~ p^2 \mid (x,n) $.
- allora $ ~ n = p_1p_2 \cdots p_k $. Per lo stesso motivo di prima, i numeri tali che $ ~ (x,n) = p_1p_2\cdots p_{k-1} $ li devo moltiplicare tra loro. Ma qua entra in gioco il caso dimostrato da Boll... notate che il loro prodotto è congruo a -1 modulo $ ~ p_k $.
Ma la tesi è ancora deboluccia, caro piever.
A chi generalizza il problema ai gruppi abeliani, va in premio un abelian grape:
La generalizzazione ai gruppi abeliani non funziona subito, ad esempio basta prendere un qualsiasi gruppo ciclico di ordine dispari e la permutazione identica, per vedere che dopo aver composto tutto ottengo ancora una permutazione.
Per i gruppi abeliani di ordine pari, funziona più o meno per lo stesso argomento di Boll.
Per $ ~ \mathbb{Z}_2^2 $ da quello che ho provato funziona, non so perchè.
Quindi sarebbe interessante vedere per quali gruppi abeliani finiti, per ogni permutazione f degli elementi di G, esistono $ ~ a,b \in G $ tali che
$ ~ af(a) = bf(b) $.
Per i gruppi abeliani di ordine pari, funziona più o meno per lo stesso argomento di Boll.
Per $ ~ \mathbb{Z}_2^2 $ da quello che ho provato funziona, non so perchè.
Quindi sarebbe interessante vedere per quali gruppi abeliani finiti, per ogni permutazione f degli elementi di G, esistono $ ~ a,b \in G $ tali che
$ ~ af(a) = bf(b) $.