# How to prove that $\frac{(5m)!(5n)!}{(m!)(n!)(3m+n)!(3n+m)!}$ is a natural number?

How to prove that $$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$ is a natural number $\forall m,n\in\mathbb N$ , $m\geqslant 1$ and $n\geqslant 1$?

-

Let $p$ be a prime number. You should show that

$$\left\lfloor \frac{5m}{p^k}\right\rfloor+\left\lfloor \frac{5n}{p^k}\right\rfloor \geq \left\lfloor \frac{m}{p^k}\right\rfloor+\left\lfloor \frac{n}{p^k}\right\rfloor+\left\lfloor \frac{3m+n}{p^k}\right\rfloor+\left\lfloor \frac{3n+m}{p^k}\right\rfloor$$

for $k \geq 1.$ By Hermite's identity you will get

$$\left\lfloor \frac{5m}{p^k}\right\rfloor=\left\lfloor \frac{m}{p^k}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{1}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{2}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{3}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{4}{5}\right\rfloor$$

Then you should show that

$$\sum_{i=1}^{4} \left\lfloor \frac{m}{p^k}+\frac{i}{5}\right\rfloor+\sum_{j=1}^{4}\left\lfloor \frac{n}{p^k}+\frac{j}{5}\right\rfloor \geq \left\lfloor \frac{3m+n}{p^k}\right\rfloor+\left\lfloor \frac{3n+m}{p^k}\right\rfloor$$

which can be done by considering different cases for the values $\frac{m}{p^k}, \frac{n}{p^k}$ i.e. each can be in the following intervals $(0,\frac15), [\frac15, \frac25), [\frac25, \frac35), [\frac35, \frac45), [\frac45, 1),$ since $\lfloor x+n \rfloor=\lfloor x\rfloor+n,$ for and real number $x$ and an integer $n,$ you can just ignore the case when $\frac{m}{p^k}, \frac{n}{p^k}$ are bigger that $1.$

Earlier thought: The expression can be rewritten as

$$\frac{\binom{5m}{3m}(3m)!\binom{5n}{n}n!}{(3m+n)!} \frac {\binom{4n}{3n}(3n)!\binom{2m}{m}m!}{(3n+m)!}$$

I was hoping to find a combinatorial interpretation for this expression but I haven't found yet!

-

If $m=n$ this is $\binom{5m}{m} ^ 2$

Assume $m>n$

$$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$

$$= \frac{(4m+(m-n)+n)! \cdot (4n-(m-n)+m)!}{m! \cdot n! \cdot (4m-(m-n))! \cdot (4n+(m-n))!}$$

$$= \frac{(4m-(m-n)+n+2(m-n))! \cdot (4n+(m-n)+m-2(m-n))!}{n! \cdot (4m-(m-n))! \cdot m! \cdot (4n+(m-n))!}$$

$$= \binom{4m-(m-n)+n}{n}\cdot\frac{(4m-(m-n)+n+2(m-n))!}{(4m-(m-n)+n)!} \cdot\binom{4n+(m-n)+m}{m}\cdot\frac{(4n+(m-n)+m-2(m-n))!}{(4n+(m-n)+m)!}$$

$$= \binom{3m+2n}{n}\cdot\frac{(5m)!}{(3m+2n)!} \cdot\binom{3n+2m}{m}\cdot\frac{(5n)!}{(3n+2m)!}$$

$$= \binom{3m+2n}{n} \cdot\frac{(5m)!}{(3m+2n)!} \cdot\frac{(5m-(3m+2n))!}{(5m-(3m+2n))!} \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3n+2m)!}$$

$$\cdots 5n<3n+2m$$

$$= \binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot (5m-(3m+2n))! \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3n+2m)!}$$

$$= \binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m} \cdot \frac{(2m-2n)! (5n)!}{(3n+2m)!}$$

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m}} {\binom{3n+2m}{5n}}$$

Consider the last factor and the denominator: $$\frac{\binom{3n+2m}{m}} {\binom{3n+2m}{5n}}$$ $$= \frac{\frac{(3n+m)\cdots(3n+2m)}{m!}} {\frac{(2m-2n)\cdots(2m+3n)}{(5n)!}}$$ $$= {\frac{(m+3n)\cdots(2m+3n)}{(2m-2n)\cdots(2m+3n)}} \cdot {\frac{(5n)!}{m!}}$$

Cases: ($m\le5n$ or $m>5n$) and ($m+3n<2m-2n$ or $m+3n\ge2m-2n$)
i.e. ($m\le5n$ or $m>5n$) and ($5n<m$ or $5n\ge m$)
i.e. $m\le5n$ or $m>5n$

Case: $m\le5n$ i.e. $2m-2n \le m+3n$
$$= {\frac{(m+1)\cdots(5n)}{(2m-2n)\cdots(m+3n-1)}}$$

Case: $m>5n$ i.e. $2m-2n > m+3n$
$$= {\frac{(m+3n)\cdots(2m-2n-1)}{(5n+1)\cdots(m)}}$$

There's probably a simple final step now that I don't know/see at the moment...

Alternatively:

$$= \binom{3m+2n}{n} \cdot\frac{(5m)!}{(3n+2m)!} \cdot\frac{(5m-(3n+2m))!}{(5m-(3n+2m))!} \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3m+2n)!}$$

$$\cdots 5n<3m+2n$$

$$= \binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m} \cdot\frac{(3m-3n)! (5n)!}{(3m+2n)!}$$

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m}} {\binom{3m+2n}{5n}}$$

Another:

$$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$

$$= \frac{(5m)!}{m!(4m)!}\cdot(4m)! \cdot \frac{(5n)!}{n!(4n)!}\cdot(4n)! \cdot \frac{1} {(3m+n)! \cdot (3n+m)!}$$

$$= \frac{(5m)!}{m!(4m)!} \cdot \frac{(5n)!}{n!(4n)!} \cdot \frac{(4m)!\cdot(4n)!} {(4m-(m-n))! \cdot (4n+(m-n))!}$$

$$= \frac{(5m)!}{m!(4m)!} \cdot \frac{(5n)!}{n!(4n)!} \cdot \frac{(4m)!} {(4m-(m-n))!(m-n)!} \cdot\frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!}$$

$$= \frac{\binom{5m}{m}\binom{5n}{n}\binom{4m}{m-n}}{\binom{4n+(m-n)}{m-n}}$$

$$\dots \space\text{using} \space\binom{n}{r}\binom{n-r}{k}=\binom{n}{k}\binom{n-k}{r}$$

$$= \frac{\binom{5n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n+(m-n)}{m-n}}$$

$$= \frac{\binom{5n}{n}\binom{4n}{k}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n}{k}\binom{4n+(m-n)}{m-n}}$$

$$\dots \space\text{and again for some}\space k : \space 0\leq k\leq 4n$$

$$= \frac{\binom{5n}{k}\binom{5n-k}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n+(m-n)-k}{m-n}\binom{4n+(m-n)}{k}}$$

$$\dots \space\text{try}\space k=2n$$

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{2n+(m-n)}{2n}\binom{4n+(m-n)}{2n}}$$

Just considering $\frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!}$ ($= 1/\binom{4n+(m-n)}{m-n}$):

$$\frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!}$$

$$= \frac{(m-n)!^2(4n-(m-n))!\cdot(4n-(m-n)+(m-n))!} {(4n+(m-n))!(4n-(m-n))!(m-n)!}$$

$$= \frac{(m-n)!^2(5n-m)!} {(3n+m)!} \cdot\binom{4n}{m-n} \dots \text{if } 5n>m$$

and this is clearly an integer if $5n-m>3n+m$ i.e. $n>m$, but we've assumed the opposite :-(

A possibly better "assumption": Assume $m=k+n>n$

$$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$

$$= \frac{(5k+5n)! \cdot (5n)!}{(k+n)! \cdot n! \cdot (3k+4n)! \cdot (4n+k)!}$$

Applied to the above results:

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m}} {\binom{3n+2m}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{3k+5n} \cdot\binom{5n+2k}{k+n}} {\binom{5n+2k}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{2k} \cdot\binom{5n+2k}{k+n}} {\binom{5n+2k}{2k}}$$

. . .

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m}} {\binom{3m+2n}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{5n+2k} \cdot\binom{5n+2k}{n+k}} {\binom{3k+5n}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{3k} \cdot\binom{5n+2k}{n+k}} {\binom{3k+5n}{3k}}$$

. . .

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{2n+(m-n)}{2n}\binom{4n+(m-n)}{2n}}$$

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5n+5k}{k}\binom{5n+4k}{n+k}}{\binom{2n+k}{2n}\binom{4n+k}{2n}}$$

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5n+5k}{k}\binom{5n+4k}{n+k}}{\binom{2n+k}{k}\binom{4n+k}{2n}}$$

-

This is USAMO'1975 Problem 1. A proof requires the lemma below. However, I would love to see a combinatorial proof.

Lemma: Let $x,y\geq 0$. Then, $\lfloor 5x\rfloor +\lfloor 5y\rfloor \geq \lfloor x\rfloor +\lfloor y\rfloor+\lfloor 3x+y\rfloor +\lfloor 3y+x\rfloor$.

(To prove the lemma, you merely have to check the inequality when $0\leq x,y<1$. Take $u:=\lfloor 5x\rfloor$ and $v:=\lfloor 5y\rfloor$, then $x < \frac{u+1}{5}$ and $y<\frac{v+1}{5}$. The rest is done by considering $u,v\in\{0,1,2,3,4\}$, where you can also assume $u \leq v$.)

-