For all primes $p$ let $v_{p}(n)$ be the $p$-adic (normed, additive) valuation of $n$, thus the greatest integer $k$ such that $p^{k}|n$. Lemma 1 (well known): $v_{p}(n!) = \sum_{k=1}^\infty \left\lfloor \frac{n}{p^{k}}\right\rfloor$. Lemma 2 (trivial): $m|n \iff v_{p}(m) \leq v_{p}(n)$ for all primes $p$. Proof of the theorem itself: By lemma 2, we just need to show that $v_{p}(m! n! (m+n)!) \leq v_{p}((2m)! (2n)!)$ (for all primes $p$). By lemma 1, we have: \[v_{p}(m! n! (m+n)!) = v_{p}(m!)+v_{p}(n!)+v_{p}((m+n)!) = \sum_{k=1}^\infty \left\lfloor \frac{m}{p^{k}}\right\rfloor+\left\lfloor \frac{n}{p^{k}}\right\rfloor+\left\lfloor \frac{m+n}{p^{k}}\right\rfloor\] and \[v_{p}((2m)! (2n)!) = v_{p}((2m)!)+v_{p}((2n)!)= \sum_{k=1}^\infty \left\lfloor \frac{2m}{p^{k}}\right\rfloor+\left\lfloor \frac{2n}{p^{k}}\right\rfloor ,\] thus it suffices to show that \[\left\lfloor \frac{m}{x}\right\rfloor+\left\lfloor \frac{n}{x}\right\rfloor+\left\lfloor \frac{m+n}{x}\right\rfloor \leq \left\lfloor \frac{2m}{x}\right\rfloor+\left\lfloor \frac{2n}{x}\right\rfloor\] for all positive reals $x$ (here $m,n$ can be real, too). If we write $m=ax+r$ and $n=bx+s$ with $0\leq r,s <x$, we get that the required inequality is equivalent to \[a+b+a+b \left\lfloor \frac{r+s}{x}\right\rfloor \leq 2a+\left\lfloor \frac{2r}{x}\right\rfloor+2b+\left\lfloor \frac{2s}{x}\right\rfloor,\] so we simply want to show that $\left\lfloor \frac{r+s}{x}\right\rfloor \leq \left\lfloor \frac{2r}{x}\right\rfloor+\left\lfloor \frac{2s}{x}\right\rfloor$. But thats rather trivial: We have $0 \leq r+s < 2x$, and if $r+s<x$, the statement is obvious. Otherwise we have $r+s \geq x$ implying that at least one of the numbers $r,s$ (w.l.o.g. $r$) is $\geq \frac{x}{2}$. We then have $\left\lfloor \frac{r+s}{x}\right\rfloor =1 = \left\lfloor \frac{2r}{x}\right\rfloor \leq \left\lfloor \frac{2r}{x}\right\rfloor+\left\lfloor \frac{2s}{x}\right\rfloor$ as desired.

Here is an short proof for the inequalities: $ \lfloor 2x\rfloor + \lfloor 2y\rfloor \geq \lfloor x\rfloor + \lfloor y\rfloor + \lfloor x + y\rfloor ,\forall x,y > 0$ We has : $ \lfloor 2x\rfloor = \lfloor x\rfloor + \lfloor x + \frac {1}{2}\rfloor$ Then the inequalities equivalent: $ \lfloor x + \frac {1}{2}\rfloor + \lfloor y + \frac {1}{2}\rfloor \geq \lfloor x + y\rfloor$ $ \lfloor \{x\} + \frac {1}{2}\rfloor + \lfloor \{y\} + \frac {1}{2}\rfloor \geq \lfloor \{x\} + \{y\}\rfloor$ It is true. In the same method we can prove that exist infinite $ (m,n)\in N$ for $ \frac {(2m)!(2n)!}{m!n!(m + n)!}$ is an even number.

But we can always use combinatorics to prove this!

Would you like to give a solution?

TTsphn wrote: Here is an short proof for the inequalities: $ \lfloor 2x\rfloor + \lfloor 2y\rfloor \geq \lfloor x\rfloor + \lfloor y\rfloor + \lfloor x + y\rfloor ,\forall x,y > 0$ We has : $ \lfloor 2x\rfloor = \lfloor x\rfloor + \lfloor x + \frac {1}{2}\rfloor$ Then the inequalities equivalent: $ \lfloor x + \frac {1}{2}\rfloor + \lfloor y + \frac {1}{2}\rfloor \geq \lfloor x + y\rfloor$ $ \lfloor \{x\} + \frac {1}{2}\rfloor + \lfloor \{y\} + \frac {1}{2}\rfloor \geq \lfloor \{x\} + \{y\}\rfloor$ It is true. In the same method we can prove that exist infinite $ (m,n)\in N$ for $ \frac {(2m)!(2n)!}{m!n!(m + n)!}$ is an even number. Yes ,TTsphn,we only need $ n > \sum _{\{k = 1\to \infty\}} [\frac {n}{2^k}]$

Let $ m$ and $ n$ be positive integers then prove that $ m!(n!)^{m}$ divides $ (mn)!$.

t0rajir0u wrote: Quote: Would you like to give a solution? Well I am giving you a hint try the rest yourself. See my post Related Problem: Quote: Let $ m$ and $ n$ be positive integers then prove that $ m!(n!)^{m}$ divides $ (mn)!$. There are obviously $ \frac{(mn)!}{m!(n!)^{m}}$ ways to split $ mn$ people into $ m$ groups implying the result.

I am aware of the combinatorial technique, but I have seen this problem posted several times and no one has ever offered a combinatorial solution, so I would be very interested in seeing that solution.

Let $ f(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}$ then we have $ f(m,0)=\frac{(2m)!}{m!m!}$ which is an integer for all $ m$. Also we note that $ f(m,n)=4f(m,n-1)-f(m+1,n-1)$. Now it is easy to prove the result by induction! I dont know if this is correct. Can anyone check this?

Seems to be correct. If I get it correctly you want to use induction on $ m+n$ and after that use the recursive relation(I haven't checked it yet) many times till one of the term in the sum will be of the form $ f(m+n,0)$,what is whole number,am I right?

t0rajir0u wrote: I am aware of the combinatorial technique, but I have seen this problem posted several times and no one has ever offered a combinatorial solution, so I would be very interested in seeing that solution. Note that the expression in question is the same as $ N = \frac{(2m+2n)!}{m!n!(m+n)!} \div \frac{(2m+2n)!}{(2m)!(2n)!} = \binom{2m+2n}{m,n,m+1} / \binom{2m+2n}{2m,2n}$ Imagine a group of $ 2m+2n$ people and a $ 2 \times 2$ grid of cells $ C{}_1{}_1$, $ C{}_1{}_2$, $ C{}_2{}_1$, $ C{}_2{}_2$ which can accomodate $ m$, $ n$, $ m$ and $ n$ people respectively. Define a type A partition as consisting of $ C{}_1{}_1$, $ C{}_1{}_2$ and $ S = C{}_2{}_1 \cup C{}_2{}_2$ of sizes $ m$, $ n$ and $ m+n$ respectively. Define a type B partition as consisting of $ D =C{}_1{}_1 \cup C{}_2{}_1$, $ E = C{}_1{}_2 \cup C{}_2{}_2$ of sizes $ 2m$, $ 2n$ respectively. [ There are $ \binom{2m+2n}{m,n,m+n}$ ways to slot the group of people into a type A partition and $ \binom{2m+2n}{2m,2n}$ ways to slot the group of people into a type B partition.] Each type B partition can be associated with a type A partition in a fixed number of ways (and $ N$ = the ratio of the number of type A partitions to the number of type B partitions is an integer constant) as follows:- From column $ D$, choose $ m$ people to go to $ C{}_1{}_1$ and the rest go to $ C{}_2{}_1$. [There are $ \binom{2m}{m,m}$ ways of doing this.] From column $ E$, choose $ n$ people to go to $ C{}_1{}_2$ and the rest go to $ C{}_2{}_2$. [There are $ \binom{2n}{n,n}$ ways to do this.] We then merge cells $ C{}_2{}_1$ and $ C{}_2{}_2$ to form $ S$, obtainig a type A partition. Note: $ N \not= \binom{2m}{m,m} \binom{2n}{n,n}$ because: analysing in reverse from type A partition, we note that the people in $ S$ could have come from type B partition in $ \binom{m+n}{m,n}$ no. of ways, because there are that many ways to split the people in $ S$ back into cells $ C{}_2{}_1$ and $ C{}_2{}_2$ i.e. the product $ \binom{2m}{m,m}\binom{2n}{n,n}$ would have overcounted by a constant factor of $ \binom{m+n}{m,n}$. Thus $ N = \binom{2m}{m,m}\binom{2n}{n,n} / \binom{m+n}{m,n}$ which can also be verified by expanding the latter expression in terms of factorials.

Solution attached.

Attachments:
A26.pdf (119kb)

rkeele wrote: Solution attached. Hello, Mr. Keele, you unfortunately misunderstood the problem. The problem you suggested is trivial.