OliForum Matematico

Dati $ ~k $ interi positivi $ ~a_1, \ldots , a_k $, sia $ ~n=a_1+\cdots +a_k $, e sia $ ~\displaystyle{ n \choose a_1,\ldots,a_k} $ il coefficiente multinomiale $ ~\displaystyle\frac{n!}{a_1!\cdots a_k!} $.
Sia $ ~d=(a_1,\ldots,a_k) $ il massimo comun divisore di $ ~a_1,\ldots,a_k $. Provare che $ ~\displaystyle\frac{d}{n}{ n \choose a_1,\ldots,a_k} $ è intero.

Premessa: dati $ x_1,x_2,...,x_n $ reali positivi con somma intera $ m $, se esiste un $ x_j $ non intero allora $ \sum_i{[x_i]} \le m-1 $. Si definisce $ \upsilon_p(x) $ la valutazione p-adica di x, cioè la massima potenza di p che divide x. Sappiamo inoltre che $ \upsilon_p(x!)=\sum_{j=1}^{+\infty}{[\frac{x}{p^j}]} $.

Torniamo al problema:
Siano definiti gli interi $ A_i=\frac{a_i}{d}, 1 \le i \le k $, cioè tali che $ gcd(A_1,A_2,...,A_n)=1 $. Dobbiamo mostrare che $ \prod_{i=1}^k{(dA_1)!} \cdot \sum_{i=1}^k{A_i} | ((d\sum_{i=1}^k{A_i})!) $, cioè detto in altre parole $ \sum_{i=1}^k\upsilon_p((dA_i)!)+\upsilon_p(\sum_{i=1}^k{A_i}) \le \upsilon_p((d\sum_{i=1}^k{A_i})!) $, cioè detto in altre parole $ \sum_{i=1}^k{ \sum_{j=1}^{+\infty}{[\frac{dA_i}{p^j}]}} + \upsilon_p(\sum_{i=1}^k{A_i}) \le \sum_{j=1}^{+\infty}{[\frac{d\sum_{i=1}^k{A_i}}{p^j}]} $ (si noti che fin qui non abbiamo fatto niente ).
Adesso detto $ \upsilon_p(\sum_{i=1}^k{A_i})=\alpha \in \mathbb{N} $ abbiamo che per quanto detto nella premessa (poichè esiste un $ A_i \not \equiv 0 \pmod p $) : $ \sum_{i=1}^k{[\frac{dA_i}{p^j}]} \le [\frac{d\sum_{i=1}^k{A_i}}{p^j}]-1 $, per ogni $ \upsilon_p(d)+ $ $ 1 \le j \le \alpha $ $ +\upsilon_p(d) $ , e ciò equivale esattamente alla tesi.

Edit: aggiunte le due $ \upsilon_p(d) $ all'ultima riga grazie a Tibor

Jordan, la tua dimostrazione fallisce nel passaggio finale se, ad esempio, $ ~k=p $, $ ~a_1=\cdots=a_p=p $. In questo caso, $ ~d=p $, $ ~\alpha=1 $, ma per $ ~j=1 $ la disuguaglianza non è verificata.

Posto anch'io la mia soluzione. Sembra lunga, ma in realtà è corta (buffo, eh? ).

Induzione su $ ~k $: per $ ~k=1 $ non v'è nulla da dimostrare; per $ ~k=2 $, posto $ ~a_i=d\cdot a'_i $, si ha

$ ~\displaystyle {a_1+a_2 \choose a_1, a_2} = \frac{a_1+a_2}{a_1}{a_1+a_2-1\choose a_1-1,a_2} = \frac{a'_1+a'_2}{a'_1}{a_1+a_2-1\choose a_1-1,a_2}. $

Poiché $ ~a'_1 $ è coprimo con $ ~a'_1+a'_2 $, deve dividere $ ~\displaystyle {a_1+a_2-1\choose a_1-1,a_2}, $ ed in tal caso

$ ~\displaystyle \frac{d}{a_1+a_2}{a_1+a_2 \choose a_1, a_2} = \frac{1}{a'_1+a'_2}{a_1+a_2 \choose a_1, a_2} = \frac{1}{a'_1}{a_1+a_2-1\choose a_1-1,a_2} $

è un intero.

Passo induttivo: per $ ~k\geq 3 $ si osserva che

$ ~\displaystyle {a_1+\cdots +a_k\choose a_1,\ldots,a_k} = {a_1+\cdots +a_k\choose a_1+a_2, a_3,\ldots,a_k}{a_1+a_2\choose a_1,a_2}. $

Allora, per ipotesi induttiva sui due multinomiali a destra ($ ~k:=2 $ e $ ~k:=k-1 $), si ha che $ ~\displaystyle {a_1+\cdots +a_k\choose a_1,\ldots,a_k} $ è multiplo di

$ ~\displaystyle \frac{(a_1+\cdots +a_k)(a_1+a_2)}{MCD(a_1+a_2,a_3,\ldots ,a_k)\cdot MCD(a_1,a_2)} = \frac{(a_1+\cdots +a_k)(a'_1+a'_2)}{MCD(a_1+a_2,a_3,\ldots ,a_k)}. $

Per concludere, basta mostrare che questo numero (intero) è a sua volta multiplo di $ ~\displaystyle \frac{a_1+\cdots +a_k}{MCD(a_1,\ldots, a_k)} $, o equivalentemente che

$ ~\displaystyle \frac{MCD(a_1,\ldots, a_k)\cdot (a'_1+a'_2)}{MCD(a_1+a_2,a_3,\ldots ,a_k)} = \frac{MCD(MCD(a_1,a_2), a_3,\ldots, a_k)\cdot (a'_1+a'_2)}{MCD(a_1+a_2,a_3,\ldots ,a_k)} $

è un intero.

Sia dunque $ ~p^\alpha $ una potenza di un primo che divide il denominatore, e mostriamo che divide anche il numeratore. Poiché $ ~p^\alpha $ divide $ ~a_3,\ldots, a_k $, la massima potenza ($ ~\leq \alpha $) di $ ~p $ che divide $ ~MCD(MCD(a_1,a_2), a_3,\ldots, a_k) $ è la stessa che divide $ ~MCD(a_1,a_2) $, e sia essa $ ~p^\beta $. Ma $ ~p^\alpha $ divide anche $ ~a_1+a_2 = MCD(a_1,a_2)\cdot(a'_1+a'_2) $, quindi sicuramente $ ~p^{\alpha-\beta} $ divide $ ~a'_1+a'_2 $. Ergo $ ~p^\alpha $ divide il numeratore.

Tibor Gallai ha scritto:$ ~\displaystyle {a_1+a_2 \choose a_1, a_2} = \frac{a_1+a_2}{a_1}{a_1+a_2-1\choose a_1-1,a_2} $

Bella questa

Ps. potevi pure correggerla però la mia, ci mancava solo due numeretti

Mah perché complicarsi la vita così?

Lemmino: un prodotto di t numeri consecutivi è divisibile per t!
Infatti $ \displaystyle~\frac{x(x-1)\cdots(x-t+2)(x-t+1)}{t!}=\binom{x}{t} $, che è intero.

Passiamo al problema. Prendiamo un primo p e dimostriamo che $ \displaystyle~\upsilon_p(a_1\cdots a_k)\le \upsilon_p(d(n-1)!) $. Poniamo $ \displaystyle~s_i=\upsilon_p(a_i)~~\forall~1\le i\le k $. Riordiniamo gli $ \displaystyle~a_i $ in modo che $ \displaystyle~\min\{s_i\}=s_k $. Grazie al lemma sappiamo che $ \displaystyle~a_1! $ divide i primi $ \displaystyle~a_1 $ fattori di n! e così via fino a $ \displaystyle~a_{k-1} $. Il problema si riduce a dimostrare che $ \displaystyle~a_k!|d(n-1)\cdots(n-a_k+2)(n-a_k+1) $.
Se $ \displaystyle~s_k=0 $, allora $ \displaystyle~a_k!|(n-1)\cdots(n-a_k+2)(n-a_k+1) $ (dato che tutti i p nella fattorizzazione di $ \displaystyle~k! $ stanno in $ \displaystyle~(k-1)! $), altrimenti, dal momento che $ \displaystyle~a_k!|n(n-1)\cdots(n-k+1) $, deve essere che $ \displaystyle~p^c|n,~~0\le c\le s_k $; per il riordinamento fatto sappiamo però che $ \displaystyle~p^{s_k}|d $, da cui $ \displaystyle~p^c|d $.

Ah, bella la dimostrazione di kn, peccato che tra i vari typo e la disorganizzazione generale ci abbia messo mezz'ora per capirla (giuro!).

La sbroglio un pochino e la riscrivo (non me ne voglia kn, a cui va il merito di averla trovata!! ).

Fissiamo un primo $ ~\displaystyle p $, e dimostriamo che la nostra frazione, ridotta ai minimi termini, non può avere un fattore $ ~\displaystyle p $ a denominatore. Così facendo, avremmo dimostrato che il denominatore è $ ~\displaystyle 1 $, e quindi la frazione è in effetti un intero.

La massima potenza di $ ~\displaystyle p $ che divide $ ~\displaystyle d $ è pari a quella che divide un certo $ ~\displaystyle a_i $ (per un opportuno $ ~\displaystyle i $), per definizione di massimo comun divisore.
Ma, poiché

$ ~\displaystyle \frac{d}{n}{n \choose a_1,\ldots,a_k} = \frac{d}{a_i}{n-1 \choose a_1,\ldots, a_{i-1},a_i-1,a_{i+1},\ldots,a_k}, $

tutti i $ ~\displaystyle p $ della fattorizzazione di $ ~\displaystyle a_i $ si semplificano con quelli di $ ~\displaystyle d $.
CVD

Ooops, le ultime due righe sono incomprensibili... Magicamente qualche $ \displaystyle~a_k $ è diventato k... Bellissimo come Tibor ha riscritto la mia soluzione in una forma molto più compatta , ma se voleste tentare di interpretare quello che ho scritto io, un ottimo test di filologia , ecco la soluzione del test (sperando che questa sia chiara):

( D'ora in poi faremo finta che p sia l'unico primo che dà problemi, quindi dove ho scritto $ \displaystyle~A|B $, prendetelo come $ \displaystyle~\upsilon_p(A)\le\upsilon_p(B) $ )

Se $ \displaystyle~s_k=0 $:
tutti i p nella fattorizzazione di $ \displaystyle~a_k! $ stanno in $ \displaystyle~(a_k-1)! $, e quindi per il lemma $ \displaystyle~a_k!|(n-1)\cdots(n-a_k+2)(n-a_k+1) $, perciò $ \displaystyle~a_k!|d(n-1)\cdots(n-a_k+2)(n-a_k+1) $

Se $ \displaystyle~s_k>0 $:
come prima si semplificano tutti i primi di $ \displaystyle~(a_k-1)! $. Se $ \displaystyle~a_k!|(n-1)\cdots(n-a_k+2)(n-a_k+1) $ siamo a posto. Altrimenti, poniamo $ \displaystyle~c=\upsilon_p(a_k!)-\upsilon_p[(n-1)\cdots(n-a_k+2)(n-a_k+1)] $ (il numero di p di $ \displaystyle~a_k! $ che non si sono ancora semplificati). Deve essere $ \displaystyle~c \le s_k $ (rimangono al massimo tutti i p di $ \displaystyle~a_k $). Vogliamo mostrare che $ \displaystyle~p^c $ si semplifica del tutto con d. Per il riordinamento fatto sappiamo però che $ \displaystyle~p^{s_k}|d $ (dato che $ \displaystyle~s_k $ è il più piccolo $ \displaystyle~s_i $, divide il MCD), da cui $ \displaystyle~p^c|d $.

Tibor Gallai ha scritto: Fissiamo un primo $ ~\displaystyle p $, e dimostriamo che la nostra frazione, ridotta ai minimi termini, non può avere un fattore $ ~\displaystyle p $ a denominatore. Così facendo, avremmo dimostrato che il denominatore è $ ~\displaystyle 1 $, e quindi la frazione è in effetti un intero.

Scusami, puoi chiarire meglio questo concetto?...non sono sicuro di aver capito a pieno...
Perchè il fatto che a denominatore non ci siano fattori $ ~\displaystyle p $ implica che il denominatore sia $ ~\displaystyle 1 $?
Grazie in anticipo.

gismondo ha scritto:Perchè il fatto che a denominatore non ci siano fattori $ ~\displaystyle p $ implica che il denominatore sia $ ~\displaystyle 1 $?

Perché se lo facciamo per un primo generico, lo possiamo fare per ogni primo. Ovviamente, l'$ ~a_i $ che prendiamo più avanti dipende da p, ma questo non compromette nulla.

Son proprio contento di avere trovato una bella soluzione per questo problema, che utilizza la combinatoria. Non spaventatevi per la lunghezza sono solo stato un po' prolisso, in maniera che si capisse bene. Un partecipante di Cesenatico la può capire benissimo, se ci si mette.

Premessa: come molti di voi sanno (e come è scritto qua), il coefficiente multinomiale $ ~\displaystyle{ n \choose a_1,\ldots,a_k}=~\displaystyle\frac{n!}{a_1!\cdots a_k!} = E $ (per comodità) indica il numero di anagrammi di una parola di $ n $ lettere in cui la prima lettera è ripetuta $ a_1 $ volte, la seconda $ a_2 $ volte e così via fino alla k-esima che è ripetuta $ a_k $ volte.

Con questa osservazione, la tesi del problema diventa equivalente a mostrare che $ E $ è multiplo di $ \frac nd $ (che è un numero intero) dove $ n $ è il numero delle lettere della parola e $ d $ è l'MCD delle volte che si ripetono le lettere.

Immaginiamo che ci sia una lettera che si ripeta proprio $ d $ volte e che, per comodità, chiameremo 'A'. Prendiamo un'anagramma della parola, a cui sono state tolte le lettere 'A'. Ora costruiamo un'anagramma aggiungendo le lettere 'A' una ad una. Bene, a partire da un'anagramma senza 'A', quanti diversi angrammi della parola completa posso costruire? Posso mettere la prima 'A' in prima posizione, davanti a tutte le lettere, o dopo la prima e così via, fino a dopo l'ultima. In totale sono $ n-d+1 $ scelte. La seconda 'A' avrà analogamente $ n-d+2 $ scelte, fino alla d-esima 'A' con $ n $ scelte. Dobbiamo poi dividere per le permutazioni delle 'A', che sono $ d! $.
Pertanto avremo $ ~\displaystyle{ \frac {n \cdot (n-1) \cdots (n-d+1)}{d!} = \frac nd \cdot {n-1 \choose d-1} $ anagrammi.

E' chiaro che se partiamo da due anagrammi diversi della parola a cui sono state tolte le lettere 'A' e aggiungiamo le lettere 'A', otterremo ancora anagrammi diversi. D'altra parte, in questo modo, riusciamo a scrivere tutti gli $ E $ anagrammi della parola, partendo dai diversi anagrammi della parola senza le lettere 'A'. Abbiamo quindi trovato che $ E $ è un multiplo di $ \frac nd $ (abbiamo fatto dei mucchi di anagrammi tutti multipli di $ \frac nd $) e il problema è risolto.

Se invece non c'è una lettera 'A' che si ripete esattamente $ d $ volte, essendo $ d $ l'MCD delle volte che si ripetono le lettere, possiamo comunque trovare $ h $ lettere 'B1', 'B2', 'B3', ..., 'Bh' che si ripetono rispettivamente $ m_1d $, $ m_2d $, ..., $ m_hd $ volte e tali che $ MCD(m_1, \cdots, m_h)=1 $. Facendo l'analogo ragionamento che abbiamo fatto sulla lettera 'A' su ciascuna di queste lettere otteniamo che $ E $ è un "multiplo" di $ \frac{n}{m_1d} $, $ \frac{n}{m_2d} $, ... e $ \frac{n}{m_hd} $. Ho scritto "multiplo" virgolettato e in corsivo, perché $ \frac{n}{m_1d} $, $ \frac{n}{m_2d} $, ... e $ \frac{n}{m_hd} $ non sono necessariamente dei numeri interi, ma possono essere anche delle frazioni. Poco male! Quello che otteniamo, in realtà, è che $ \frac nd $ è un divisore di $ m_1E $, $ m_2E $, ... e $ m_hE $, dal momento che $ E $ può essere scritto come prodotto di un numero intero per $ \frac{n}{m_1d} $, o di un altro numero intero per $ \frac{n}{m_2d} $ e così via...

Per il teorema di Bezout, essendo $ MCD(m_1, \cdots, m_h)=1 $, possiamo trovare dei numeri interi $ c_1 $, ..., $ c_h $ per cui $ c_1m_1E + c_2m_2E + \cdots + c_hm_hE = E $. Ma allora $ \frac nd $ è divisore di questa somma, in quanto divisore di tutti i fattori e pertanto abbiamo trovato che $ E $ è divisibile per $ \frac nd $.

Il problema è quindi risolto e un grazie a Tibor Gallai per il consulto di questa notte alle 2:30.

Se qualcuno (anche uno che non ha mai postato!) non capisce qualcosa, chieda pure!

Aaah, peccato che usi Bezout alla fine, avevo sperato che esistesse un modo solo combinatorio di dimostrarlo. Bella idea per concludere, però!!

Quella di Harry Potter tra l'altro è la soluzione ufficiale di Dan Schwarz

Tibor Gallai ha scritto:Aaah, peccato che usi Bezout alla fine, avevo sperato che esistesse un modo solo combinatorio di dimostrarlo. Bella idea per concludere, però!!

Mi sembra che la dimostrazione di Edriv sia puramente combinatoria (sebbene scritta in linguaggio cannoneggiante con orbite e stabilizzatori). Assomiglia alla dimostrazione del piccolo teorema di Fermat "con le collane".
Idea:
1) multinomiale = numero di anagrammi di una parola di n lettere, di cui $ a_1 $ uguali tra loro, $ a_2 $ uguali tra loro (e diverse dalle precedenti), $ a_3 $ uguali tra loro e diverse dalle precedenti, and so on.
2) contiamo gli anagrammi in questo modo: mettiamo nella stessa "scatola" un anagramma e tutte le sue versioni "shiftate": per esempio, nella scatola con AABCB ci vanno ABCBA, BCBAA, CBAAB, BAABC.
3) dimostriamo che in ogni scatola c'è un mutiplo di n/d elementi, in questo modo: prendiamo k il più piccolo intero per cui stringa shiftata k volte = stringa originale. E' facile vedere che nella scatola ci sono k stringhe, e che per ogni i il numero delle lettere a_i è un multiplo di n/k. Quindi...

Arf.