greentreeroad wrote:

When I saw the problem I solved it the same way as the official solution. But that was only because i had seen the nice solution to $ \frac{(n,m)}{n} \binom{n}{m}$ is an integer.

greentreeroad wrote:

That's just too cool.... For the sake of completeness, here's the prime factor counting solution: We want to show that $ \frac {n}{d} | \binom{n}{a_1,a_2,\cdots,a_k}$. Let $ p$ be a prime divisor of the LHS. It is sufficient to show that for each $ 1 \le i \le k$ we have: $ v_p(n) - v_p(a_i) \le v_p(n!) - \sum_{i = 1}^{k} v_p(a_i!)$ Recall that $ v_p(t!) = \sum_{i = 1}^{\infty} \left\lfloor \frac {t}{p^i} \right\rfloor$, and notice that $ v_p(t) = v_p(t!) - v_p((t - 1)!) = \sum_{i = 1}^{\infty} \left\lfloor \frac {t}{p^i} \right\rfloor - \left\lfloor \frac {t - 1}{p^i} \right\rfloor$ So it is enough to show that for any $ i \in \mathbb{N}$ and $ 1 \le j \le k$, we have: $ \left\lfloor \frac {n}{p^i} \right\rfloor - \left\lfloor \frac {n - 1}{p^i} \right\rfloor - \left\lfloor \frac {a_j}{p^i} \right\rfloor + \left\lfloor \frac {a_j - 1}{p^i} \right\rfloor \le \left\lfloor \frac {n}{p^i} \right\rfloor - \sum_{i = 1}^{k} \left\lfloor \frac {a_i}{p^i} \right\rfloor$ Or: $ \left\lfloor \frac {n - 1}{p^i} \right\rfloor \ge \sum_{i \neq j} \left\lfloor \frac {a_i}{p^i} \right\rfloor + \left\lfloor \frac {a_j - 1}{p^i} \right\rfloor$ But this is true - it is the opposite of the triangle inequality for the floor function. Proof of this property of $ \left\lfloor x \right\rfloor$:

My solution uses a well known problem in number theory $ d=\gcd(a_1,..,a_n)$ ,we can find $ (x_1,..,x_n)\in \mathbb{Z}^n$ such that $ \sum_{i=1}^n a_ix_i=n$ .Thus we can write this number in the form : \[ \frac{d.(n-1)!}{\prod_{i=1}^n (a_i)!} =\sum_{i=1}^n x_i \binom{n}{a_i-1,a_{i+1},\cdots,a_{i-1}} \] and obvious this number is an integer .

TTsphn wrote: My solution uses a well known problem in number theory $ d = \gcd(a_1,..,a_n)$ ,we can find $ (x_1,..,x_n)\in \mathbb{Z}^n$ such that $ \sum_{i = 1}^n a_ix_i = n$ .Thus we can write this number in the form : \[ \frac {d.(n - 1)!}{\prod_{i = 1}^n (a_i)!} = \sum_{i = 1}^n x_i \binom{n}{a_i - 1,a_{i + 1},\cdots,a_{i - 1}} \] and obvious this number is an integer . You mean $ \sum_{i = 1}^n a_ix_i = d$. It was the same solution greentreeroad stated

We don't even need Bezout's Lemma (the fact that the GCD of some numbers is a linear combination of them over $ \mathbb{Z}$)! $ \frac{n}{a_i} | \binom{n}{a_1,\cdots,a_k}$ holds for each $ i$ from the identity $ \frac{a_i}{n}\binom{n}{a_1,\cdots,a_k}=\binom{n-1}{a_1,\cdots,a_{i-1},a_i-1,a_{i+1},\cdots,a_k}$. Thus, $ [\frac{n}{a_1},\cdots,\frac{n}{a_k}] | \binom{n}{a_1,\cdots,a_k}$. But this lcm is actually $ \frac{n}{d}$! ([] means LCM) Analyzing my solution again, It seems as if it is not so different than greentreeroad or TTsphn solutions: I showed that the problem is equivalent to showing that for any $ i$: $ \sum_{k=1}^{\infty} \left\lfloor \frac {n - 1}{p^k} \right\rfloor \ge \sum_{k=1}^{\infty} \sum_{i \neq j} \left\lfloor \frac {a_i}{p^k} \right\rfloor + \left\lfloor \frac {a_j - 1}{p^k} \right\rfloor$ Which is the same as $ \binom{n-1}{a_1,\cdots,a_{i-1},a_i-1,a_{i+1},\cdots,a_k}$ being an integer...

Let $ Z=\frac{d \cdot (n-1)!}{\prod^k_{i=1} (a_i!)}$. Also let $ b_i=\frac{a_i}d$ for all $ i$. $ (a_1+\ldots+a_{k-1})!$ is divisible by $ a_1!a_2!\ldots a_{k-1}!$, and $ (a_1+\ldots+a_{k-1}+1)(a_1+\ldots+a_{k-1}+2)\ldots(n-1)$ is divisible by $ (a_k-1)!$. So $ Zb_k$ is an integer. Similarly, $ Zb_i$ is integer for any $ i$. But $ gcd(b_1,b_2,\ldots,b_k)=1$, so $ Z$ must be an integer. I'm not sure with this solution, especially the last part (it's just intuitive). Please correct me if I'm wrong.

Use $v_p(a!)=(n-s_p(a))/(p-1)$ and then use $s(a_1)+...+s(a_k)=s(n)-(p-1)X$ where $X$ is number of carryovers

First lemma : $v_p(n!) = \frac{n - s_p(n)}{p - 1}$ where $v_p(x) =$ the exponent of $p$ in $x$ and $s_p(x) =$ the sum of digits of $x$ in base $p$. Second lemma : $(p - 1)v_p(a) + s_p(a) = 1 + s_p(a - 1)$ . Proof of lemma 2: $v_p(n!) = v_p(n) + v_p((n - 1)!)$ and using lemma 1 we have the conclusion . Now it is obvious that : $v_p(d) = min(v_p(a_i))$ .Let's suppose that we have this minimum for $a_1$ . Using lemma1 we conclude that we need to solve this: $(p - 1) v_p(a_1) + s_p(a_1) + ... + s_p(a_n) \ge (p -1)v_p(n) + s_p(n)$ Using lemma2 we have to show that: $1 + s_p(a_1 - 1) + s_p(a_2) + ... + s_p(a_k) \ge 1 + s_p(n - 1)$ so we need to show that : $s_p(a_1 - 1) + s_p(a_2) + ... + s_p(a_k) \ge s_p(a_1 - 1 + a_2 + ... + a_k)$ Using that $s_p(x) + s_p(y) \ge s_p(x + y)$ we have the conclusion.

By Bezout's lemma, let $d=\sum_{i=1}^{k}a_ib_i$ where $b_i\in\mathbb{Z}.$ Notice that $$\frac{d}{n}\cdot\frac{n!}{\prod_{i=1}^{k}{(a_i!)}}=\frac{n!}{\prod_{i=1}^{k}{(a_i!)}}\sum_{i=1}^{k}{\frac{a_ib_i}{n}}=\sum_{i=1}^{k}{\left(b_i\cdot\frac{n!}{n}\cdot\frac{a_i}{\prod_{i=1}^{k}{(a_i)!}}\right)}=\sum_{i=1}^{k}{b_i\binom{n-1}{a_1,.,a_i-1,.,a_k}}$$which is an integer. $\square$

Take $v_p$ for an arbitrary prime $p$. Using the identity $v_p(n!)=\frac{n-s_p(n)}{p-1},$ this reduces to showing that $$(p-1)v_p(d)+s_p(a_1)\cdots+s_p(a_n)\geq s_p(n)+(p-1)v_p(n).$$Note that $$s_p(a_1)\cdots+s_p(a_n)-s_p(n)$$is $p-1$ times the number of carry-overs when adding $a_1+a_2\cdots +a_n$. Let this be $C$. Then, we just want to show that $$C\geq v_p(n)-v_p(d).$$Consider adding $a_1+a_2\cdots +a_n$. We know that all digits after $v_p(n)$ are zero in the final sum. However, all places on or to the left of $v_p(d)$ will have at least one addend with a non-zero digit in that place. Hence, each place value in between these two must have a carry-over, so we are done.