# An Old Number theory IMO 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!

• Wait is it $[k/p]$ or is it $[k/p]+[k/p^2]+\dotsb$? – Zach Teitler Apr 11 at 11:33
• the latter, but i thought proving using [k/p] would be equivalent / easier – Aditya_math Apr 11 at 11:46
• $m=n=p=2$ is a counterexample to what you wanted to show. Better work with the full screen version I think. – Zach Teitler Apr 11 at 12:10
• @ZachTeitler , i tried the problem again now but i'm not sure how to deal with infinite sum inequalities with floor function; can you pls give me a hint? – Aditya_math Apr 11 at 12:53
• In this answer it is shown that $$\frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1}$$ – robjohn Apr 11 at 22:46

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.

• Woah thanks so much, i guess i should have tried the second problem also as the inequality you used was the problem right before this one. Thank you once again! – Aditya_math Apr 11 at 13:16

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.

• wow, this is really cool! Thanks! – Aditya_math Apr 12 at 5:37
• @Aditya_math not as elegant as robjohn's in my opinion. I had no idea where he was going until the very last step. Beautiful. – user3733558 Apr 12 at 13:07

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

• this is really beautiful... thanks! I'll have to read this again to completely wrap my head around this – Aditya_math Apr 12 at 20:06
• I'm glad you liked this answer. However, the point of $(2)$-$(4)$ was to show $(5)$ using fractional parts; whereas Mindlack used integer parts to show the same thing with less work. Both answers aim at showing $(6)$, which by Legendre, shows $(7)$. – robjohn Apr 12 at 20:17