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

If $p$ is a prime, then the number of times $p$ divides $N!$ is $e_p(N)=\sum_{k=1}^\infty\left\lfloor\frac{N}{p^k}\right\rfloor$. So I need
$$e_p(5m)+e_p(5n)\geq e_p(m)+e_p(n)+e_p(3m+n)+e_p(3n+m).$$
What to do next?  Thanks in advance.
 A: 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! 
A: 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 x+3y\rfloor$.

Proof.  Without loss of generality, suppose that $0\leq x,y<1$.  Otherwise, replace $x$ and $y$ by $x-\lfloor x\rfloor$ and $y-\lfloor y\rfloor$, respectively.  Thus, the claim becomes
$$\lfloor 5x\rfloor+\lfloor 5y\rfloor\geq \lfloor 3x+y\rfloor+\lfloor x+3y\rfloor\text{ for }0\leq x,y<1\,.\tag{*}$$
Take $u:=\lfloor 5x\rfloor$ and $v:=\lfloor 5y\rfloor$, then $u,v\in\{0,1,2,3,4\}$, $$\dfrac{u}{5}\leq x < \dfrac{u+1}{5}\,,$$ and $$\dfrac{v}{5}\leq y<\dfrac{v+1}{5}\,.$$  Therefore,
$$\frac{3u+v}{5}\leq 3x+y<\frac{3u+v+3}{5}$$
and
$$\frac{u+3v}{5}\leq x+3y<\frac{u+3v+3}{5}\,.$$  By symmetry, we may assume further that $u\leq v$.
For convenience, write $a:=\lfloor 3u+v\rfloor$ and $b:=\lfloor u+3v\rfloor$.  We need to show that $u+v\geq a+b$.

*

*If $(u,v)=(0,0)$, then obviously $a=b=0$, whence (*) is an equality.


*If $(u,v)=(0,1)$, then $a=0$ and $b\in\{0,1\}$, so (*) is again true.


*If $(u,v)=(0,2)$, then $a=0$ and $b=1$, so (*) is a strict inequality.


*If $(u,v)=(0,3)$, then $a\in\{0,1\}$ and $b\in\{1,2\}$, so (*) is true.


*If $(u,v)=(0,4)$, then $a\in\{0,1\}$ and $b=2$, so (*) is a strict inequality.


*If $(u,v)=(1,1)$, then $a,b\in\{0,1\}$, so (*) is true.


*If $(u,v)=(1,2)$, then $a=b=1$, so (*) is a strict inequality.


*If $(u,v)=(1,3)$, then $a=1$ and $b=2$, so (*) is a strict inequality.


*If $(u,v)=(1,4)$, then $a=1$ and $b\in\{2,3\}$, so (*) is a strict inequality.


*If $(u,v)=(2,2)$, then $a,b\in\{1,2\}$, so (*) is true.


*If $(u,v)=(2,3)$, then $a,b\in\{1,2\}$, so (*) is a strict inequality.


*If $(u,v)=(2,4)$, then $a=2$ and $b\in\{2,3\}$, so (*) is a strict inequality.


*If $(u,v)=(3,3)$, then $a=b=2$, so (*) is a strict inequality.


*If $(u,v)=(3,4)$, then $a\in\{2,3\}$ and $b=3$, so (*) is a strict inequality.


*If $(u,v)=(4,4)$, then $a=b=3$, so (*) is a strict inequality.
A: I became aware of this question due to some recent edits. The shorter proofs seem to rely on
$$
\lfloor5x\rfloor+\lfloor5y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor+\lfloor3x+y\rfloor+\lfloor3y+x\rfloor
$$
My answer also uses this inequality. I have tried to provide a complete, yet shorter, proof of it.

Define
$$
f(x,y)=\lfloor5x\rfloor+\lfloor5y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor3x+y\rfloor-\lfloor3y+x\rfloor\tag1
$$
Note that $f(x+1,y)=f(x,y+1)=f(x,y)$. Thus, we only need worry about $x,y\in[0,1)$.
Let $x\in\left[\frac j5,\frac{j+1}5\right)$ and $y\in\left[\frac k5,\frac{k+1}5\right)$, where $j,k\in\{0,1,2,3,4\}$. Then
$$
\lfloor x\rfloor=\lfloor y\rfloor=0\tag{2a}
$$
$$
\lfloor5x\rfloor=j\qquad\text{and}\qquad\lfloor5y\rfloor=k\tag{2b}
$$
$$
\lfloor3x+y\rfloor\le\left\lfloor\frac{3j+k+3}5\right\rfloor
\qquad\text{and}\qquad
\lfloor x+3y\rfloor\le\left\lfloor\frac{j+3k+3}5\right\rfloor
\tag{2c}
$$
Apply $(2)$ to $(1)$:
$$
\begin{align}
f(x,y)
&=\lfloor5x\rfloor+\lfloor5y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor3x+y\rfloor-\lfloor3y+x\rfloor\\
&\ge j+k-\left\lfloor\frac{3j+k+3}5\right\rfloor-\left\lfloor\frac{j+3k+3}5\right\rfloor\\
&=g(j,k)\tag3
\end{align}
$$
Compute the values of $g(j,k)$ for $j,k\in\{0,1,2,3,4\}$:
$$
\begin{array}{c|cc}
g&0&1&2&3&4\\\hline
0&0&0&0&0&0\\
1&0&0&0&1&0\\
2&0&0&0&1&1\\
3&0&1&1&0&1\\
4&0&0&1&1&2
\end{array}\tag4
$$
Inequality $(3)$, table $(4)$, and the lattice periodicity of $f$, show that $f(x,y)\ge0$ for all $x,y$. That is,
$$
\lfloor5x\rfloor+\lfloor5y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor+\lfloor3x+y\rfloor+\lfloor3y+x\rfloor\tag5
$$
Inequality $(5)$, when combined with Legendre's Formula, yields
$$
m!\,n!\,(3m+n)!\,(m+3n)!\mid(5m)!\,(5n)!\tag6
$$
