179. ProofathonNT

[AGallese]

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)} \]

[Gerald Lambeau]

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

[Troleito br00tal]

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

[Gerald Lambeau]

Oddio che scemo!
Ora non sono più a casa, appena torno ricontrollo.

[LucaMac]

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 )

[AGallese]

Direi che va bene! Vai pure

[<enigma>]

Adesso divertitevi a dimostrare che quel prodotto è divisibile per $((n-1)!(n-2)!\cdots 2!1!)^2$.

[Gerald Lambeau]

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.

[Troleito br00tal]

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.

[<enigma>]

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?