179. ProofathonNT

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
AGallese
Messaggi: 19
Iscritto il: 02 dic 2013, 19:57

179. ProofathonNT

Messaggio da AGallese » 03 giu 2015, 16:41

Provare che per ogni scelta di interi $\{a_1, a_2, ..., a_{n+1}\}$, si ha che
\[ (n!)^2 \mid \prod_{i\neq j}{(a_i-a_j)} \]

Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: 179. ProofathonNT

Messaggio da Gerald Lambeau » 03 giu 2015, 17:23

Essendo le classi modulo $n$ in numero $n$, per pigeonhole esistono $a_k, a_m$, con $k \ne m$, tali che sia $a_k \equiv a_m \mod n$ e $a_k-a_m \equiv a_m-a_k \equiv 0 \mod n$. Dato che entrambe le differenza compaiono nella produttoria essa è divisibile per $n^2$.
Si può ripetere lo stesso ragionamento per i numeri da $n-1$ a $1$ in quanto le loro classi di resto sono minori di quelle di $n$, e in particolare il pigeonhole funziona (se per $x$ buche [le classi di resto] servono $x+1$ picconi affinché il pigeonhole funzioni, anche $x+1+y$ piccioni soddisfano).
Dunque la produttoria è divisa da $n^2(n-1)^2...2^21^2=(n!)^2$.
"If only I could be so grossly incandescent!"

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: 179. ProofathonNT

Messaggio da Troleito br00tal » 03 giu 2015, 17:28

Non proprio; tu stai dicendo (almeno credo, da quanto ho capito :) ): "se un numero è divisibile per $4$ e per $2$ allora è divisibile per $8$", cosa chiaramente falsa. Comunque, si può aggiustare.

(In particolare, chi ti dice che se $n|k,n-1|k,...,1|k$ allora $n!|k$?; a priori non è così).

Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: 179. ProofathonNT

Messaggio da Gerald Lambeau » 03 giu 2015, 17:32

Oddio che scemo! :oops:
Ora non sono più a casa, appena torno ricontrollo.
"If only I could be so grossly incandescent!"

LucaMac
Messaggi: 178
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: 179. ProofathonNT

Messaggio da LucaMac » 03 giu 2015, 19:15

Riscriviamo come $ n! \mid \prod_{j > i} (a_j - a_i) $
Proviamolo per induzione su $n$.
Passo base: $n=1$ è ovvio!
Passo induttivo: supponiamo sia vero per $n-1$ , allora è vero per $n$.
Dimostrazione: analogamente a Gerald $ \exists p > q $ tali che $ n \mid a_p - a_q $ , allora basta che vale $ (n-1)! \mid \prod_{ j > i , (j,i) \neq (p,q)} (a_j-a_i) $ . Togliendo ancora termini basta che valga (posto $b_i=a_i$ per $i < p$ e $b_i = a_{i+1} $ per $i \geq p$ ) che $(n-1)! \mid \prod_{ j>i} (b_j-b_i) $ che è vero per ipotesi induttiva!
Allora la tesi è provata per induzione su $n$ (spero di non aver fatto orrori :lol: )
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

AGallese
Messaggi: 19
Iscritto il: 02 dic 2013, 19:57

Re: 179. ProofathonNT

Messaggio da AGallese » 04 giu 2015, 11:29

Direi che va bene! Vai pure

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 179. ProofathonNT

Messaggio da <enigma> » 04 giu 2015, 12:27

Adesso divertitevi a dimostrare che quel prodotto è divisibile per $((n-1)!(n-2)!\cdots 2!1!)^2$.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: 179. ProofathonNT

Messaggio da Gerald Lambeau » 04 giu 2015, 14:01

Visto che il problema è stato risolto chiedo come avrei potuto concludere la mia soluzione, che ho continuato così:

per $n-k$ posso scegliere $k+1$ coppie distinte (con distinte intendo almeno uno dei due interi diverso da quelli di un'altra coppia), e quindi la produttoria è divisa da $(n-k)^{k+1}$.
La massima potenza di $n-k$ che divide $n!$ si calcola al seguente modo:
$\displaystyle \sum^{ \infty}_{i=1} \left [ \frac{n}{(n-k)^i} \right ]$.
Deve valere $\displaystyle \sum^{ \infty}_{i=1} \left [ \frac{n}{(n-k)^i} \right ] \le k+1$.

Chiedo se c'era una via più veloce, se ho scritto delle boiate oppure, se così è giusto, come fare per dimostrare l'ultima relazione.
"If only I could be so grossly incandescent!"

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: 179. ProofathonNT

Messaggio da Troleito br00tal » 05 giu 2015, 16:47

<enigma> ha scritto:Adesso divertitevi a dimostrare che quel prodotto è divisibile per $((n-1)!(n-2)!\cdots 2!1!)^2$.
Dato che è carino e rischia di finire nel dimenticatoio e l'avevo già visto do un hintino per questo
Testo nascosto:
Considera $v_p(roba)$ e dimostra che è $\ge$ dell'altra.

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 179. ProofathonNT

Messaggio da <enigma> » 05 giu 2015, 18:53

Troleito br00tal ha scritto:Dato che è carino e rischia di finire nel dimenticatoio e l'avevo già visto do un hintino per questo
In tal caso dò anch'io un suggerimento per una soluzione alternativa, meno naturale ma più veloce se si conosce un minimo di algebra lineare.
Testo nascosto:
Se lo riscrivo come $\prod_{i \neq j} \frac{a_i-a_j}{i-j}$ posso vederci il determinante di una matrice nota?
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Rispondi