An Old Number theory IMO question

Question

In my book, under Legendre’s Function, the following two examples were given;

When $m,n \in N$ , prove that;

1. $\ $ $m! \cdot (n!)^m$ divides $(mn)!$

2. $\ $ $m! \cdot n! \cdot (m+n)! $ divides $(2m)! \cdot (2n)!$

Well, for the first one, I know it is just the number of ways to put $mn$ balls into $m$ identical baskets, each with $n$ balls.

But, as this is a NT book, I tried solving this with Legendre’s Function and it just did not work,

I got we needed to prove:

$f(mn) \ge f(m) + m \cdot f(n)$ where $f(k) = [\frac{k}{p}]$ where [.] is the floor function.

Now, I could not figure out what to do, I tried inducting on $n$ but after using some inequalities like $[xy] \ge [x][y]$ and $[x+y] \ge [x]+[y]$ , the inequality just became false.

As I couldn't even solve the first one, I could not solve the second one either, not even 'combinatorically'.

So, I am looking for a proof of both the problems using Legendre’s Function (and perhaps a combinatorial proof of $2$ well?)

Thanks!

Answer 1

The second question follows from the following inequality: let $x,y$ be real numbers, then $[x]+[y]+[x+y] \leq [2x]+[2y]$.

Here’s a very easy proof: the inequality is unchanged when integers are added to $x,y$, so we can assume $0 \leq x,y <1$, and we want to show $[x+y] \leq [2x]+[2y]$. But $0 \leq x+y,2x,2y< 2$, so that the only case where the inequality isn’t trivial is when $[2x]+[2y]=0$, ie $[2x]=[2y]=0$, ie $x,y < 0.5$. But then $x+y <1$ and the inequality holds.

For 1), we need to show that for any prime $p$, any integers $m,n$, $\sum_{k \geq 1}{m[n/p^k]+[m/p^k]} \leq \sum_{k \geq 1}{[mn/p^k]}$. Let $l \geq 2$ be minimal such that $p^l >n$ (if $p > n$ then it’s trivial). Then for any $k \geq 1$, $[m/p^k] \leq [mn/p^{k+l-1}]$. Thus $\sum_{k \geq 1}{[m/p^k]} \leq \sum_{k \geq l}{[mn/p^k]}$. Moreover, $\sum_{k \geq 1}{m[n/p^k]} \leq \sum_{k=1}^{l-1}{m[n/p^k]} \leq \sum_{1 \leq k < l}{[mn/p^k]}$ and this ends the proof.

Answer 2

I think the combinatorial argument for 2. could go like this: let's define $g$ as the ratio $$ g(m,n) = \frac{(2m)!(2n)!}{m!n!(m+n)!} $$ We can observe that $$ g(m,n-1)=\frac{(2m)!(2n-2)!}{m!(n-1)!(m+n-1)!} = \frac{n(m+n)\color{blue}{(m+1)}}{2n(2n-1)\color{blue}{(m+1)}}g(m,n) $$ and $$ g(m+1,n-1)=\frac{(2m+2)!(2n-2)!}{(m+1)!(n-1)!(m+n)!} = \frac{n(2m+1)(2m+2)}{2n(2n-1)(m+1)}g(m,n) $$ (the blue-marked $(m+1)$ has obviously been added to match the second expression). Now, expanding the products on the respective RHS, we see that the numerators are $$ N_1=nm^2+n^2+mn+mn^2 \\ N_2=4nm^2+6nm+2n $$ and the denominator is $$ D=(4n^2-2n)(m+1) = 4n^2m+4n^2-2nm-2n $$ It's not too hard to see that $$ \begin{aligned} 4N_1-N_2 &= 4(nm^2+n^2+mn+mn^2) - (4nm^2+6nm+2n) \\ &= 4n^2m+4n^2-2nm-2n \\ &= D \end{aligned}$$ Therefore it follows that $$ \implies g(m,n)=4g(m,n-1)-g(m+1,n-1) $$ Using this formula iteratively, we can now see that $$ g(m,n) = \sum\nolimits_j \sum\nolimits_k a_{j,k} g(k,0) $$ All $a_{j,k}$ are integers and $$ g(k,0)=\frac{(2k)!}{k!k!} = \frac{(2k)!}{k!(2k-k)!} = \binom{2k}{k} $$ is a binomial coefficient.

Answer 3

Question $\bf{1}$

In this answer, it is shown that $$ \frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1}\tag1 $$

---

Question $\bf{2}$

Using the equation $x=\lfloor x\rfloor+\{x\}$, we get the equation $$ \lfloor 2x\rfloor+\lfloor 2y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor x+y\rfloor=\{x\}+\{y\}+\{x+y\}-\{2x\}-\{2y\}\tag2 $$ There are two possibilities: if $\{x\}+\{y\}\lt1$ $$ \{x+y\}=\{x\}+\{y\}\tag{3a} $$ or if $\{x\}+\{y\}\ge1$ $$ \{x+y\}=\{x\}+\{y\}-1\tag{3b} $$ If $\{x\}\lt\frac12$ and $\{y\}\lt\frac12$, then $\text{(3a)}$ implies $$ \{x\}+\{y\}+\overbrace{\{x+y\}}^{\{x\}+\{y\}}-\overbrace{\{2x\}}^{2\{x\}}-\overbrace{\{2y\}}^{2\{y\}}=0\tag{4a} $$ If $\{x\}\ge\frac12$ and $\{y\}\ge\frac12$, then $\text{(3b)}$ implies $$ \{x\}+\{y\}+\overbrace{\{x+y\}}^{\{x\}+\{y\}-1}-\overbrace{\{2x\}}^{2\{x\}-1}-\overbrace{\{2y\}}^{2\{y\}-1}=1\tag{4b} $$ Otherwise, assume $\{x\}\ge\frac12$ and $\{y\}\lt\frac12$, then if $\{x\}+\{y\}\,{\color{#C00}{\lt}\atop\color{#090}{\ge}}\,1$ $$ \{x\}+\{y\}+\overbrace{\{x+y\}}^{\{x\}+\{y\}-{\color{#C00}{0}\atop\color{#090}{1}}}-\overbrace{\{2x\}}^{2\{x\}-1}-\overbrace{\{2y\}}^{2\{y\}}={\color{#C00}{1}\atop\color{#090}{0}}\tag{4c} $$ Thus, $(2)$ and $(4)$ ensure that $$ \lfloor 2x\rfloor+\lfloor 2y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor x+y\rfloor\ge0\tag5 $$ Therefore, for any prime $p$, $$ \overbrace{\sum_{k=1}^\infty\left(\left\lfloor\frac{2n}{p^k}\right\rfloor+\left\lfloor\frac{2m}{p^k}\right\rfloor\right)}^\text{factors of $p$ in $(2n)!(2m)!$}\ge\overbrace{\sum_{k=1}^\infty\left(\left\lfloor\frac{n}{p^k}\right\rfloor+\left\lfloor\frac{m}{p^k}\right\rfloor+\left\lfloor\frac{n+m}{p^k}\right\rfloor\right)}^\text{factors of $p$ in $n!m!(n+m)!$}\tag6 $$ That is, $$ n!\,m!\,(n+m)!\mid(2n)!\,(2m)!\tag7 $$