Proving Inequality with the Greatest Integer Function

Show that

$$[(m+n)x]+[(m+n)y] \ge [mx+(n-1)y]+[my+(n-1)x]$$

where $m,~n \in \Bbb{N}$ and $0\le x,~y < 1$.

I've tried everything for about half a day and still couldn't figure it out. Actually I don't know if it is true so should I say, 'show that if it is right or not'. This question was aroused from the question, show that

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

is an integer where $m,~n$ are natural numbers. This question was so hard but I was able to prove it by seperating some cases. Then I began to wonder if I could generalize this, which is actually the same question I proposed above. At first, I thought I could replace $n-1$ into plain $n$, but I did find a counter-example for that case. So now I'm wondering if the very first proposition holds since for now I couldn't find any counter-example. So I'm guessing the inequality might be true.

Please help me! The question is killing me! It would be also glad if someone could suggest any idea to solve the second question in a simple(or brilliant) manner.

EDIT The factorial question can be reduced to proving the given inequality for the special case when $m=3,~n=2$ as Ewan Delanoy had explained well below. This implies that proving the inequality is just the same as proving that

$$\frac{(mx)!(ny)!}{x!y!(mx+(n-1)y)!(my+(n-1)x)!}$$

is an integer. We can also think about generalizing this question into proving for the case where the $x,~y$ in the denominator is something like $ax,~by$. But first I'd just be happy to know how to prove (or show counter-example) the first inequality I suggested.

• Actually I don't need 'official' source as shown below. – Taxxi Nov 22 '13 at 7:46
• What is the function $[\cdot]$ in the desired inequality? From context I'm guessing that you mean the floor function $\lfloor t \rfloor$ = greatest integer $k \leq t$; is that right? The title of the question says "Gaussian Function" but that's usually a multiple of $\exp (-C(t-t_0)^2)$ for some real $C>0$ and $t_0$, and that can't be what you mean here. – Noam D. Elkies Nov 25 '13 at 17:31
• @NoamD.Elkies I didn't know that for my short knowledge. Thanks for letting me know. – Taxxi Nov 26 '13 at 4:06

Let $m=6,n=3,x=0.10,y=0.21$. $$\lfloor(m+n)x\rfloor+\lfloor(m+n)y\rfloor=\lfloor0.90\rfloor+\lfloor1.89\rfloor=0+1=1.$$ $$\lfloor mx+(n-1)y\rfloor+\lfloor my+(n-1)x\rfloor=\lfloor1.02\rfloor+\lfloor1.46\rfloor=1+1=2.$$

I do not know if your inequality holds for every $m,n$, but I know two things :

• It is true for $m=3,n=2$.
• The case $m=3,n=2$ suffices to solve your second question.

To show that $r=\frac{(5n)!(5m)!}{n!m!(n+3m)!(m+3n)!}$ is an integer, it suffices to show that the valuation $v_p(r)$ is nonnegative for every prime $p$. But by Legendre's theorem,

$$v_p(n!)=\sum_{k=1}^{\infty} \lfloor \frac{x}{p^k} \rfloor \tag{1}$$

So it will suffice to show the following :

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

If we put $x=\frac{n}{p^k}$ and $y=\frac{n}{p^k}$, (2) is equivalent to $d(x,y) \geq 0$ where

$$d(x,y)=\big(\lfloor 5x \rfloor + \lfloor 5y \rfloor\big)- \big(\lfloor x \rfloor + \lfloor y \rfloor+ \lfloor x+3y \rfloor + \lfloor y+3x \rfloor \big) \tag{3}$$

Now $d$ is $1$-periodic in both variables $x$ and $y$, so it will suffice to show that $d(x,y)\geq 0$ when $x$ and $y$ are both in $[0,1)$. In which case (3) reduces to

$$\lfloor 5x \rfloor + \lfloor 5y \rfloor \geq \lfloor x+3y \rfloor + \lfloor y+3x \rfloor \ (\ \text{for} \ x,y\in [0,1)) \tag{4}$$

UPDATE 11/22/2013

Let us put

$$i=\lfloor 5x \rfloor, j=\lfloor 5y \rfloor, k=\lfloor x+3y \rfloor, l=\lfloor 3x+y \rfloor \tag{5}$$

and also

$$\begin{array}{lcl} \mu&=&i+j-(k+l), \\ \varepsilon&=&{\sf min}(i+1-5x,j+1-5y,k+1-(x+3y),l+1-(3x+y)) > 0. \\ \end{array} \tag{6}$$

We then have

$$\begin{array}{lcl} 4(i+j)-5(k+l) &\geq& 4(5x+5y-2+2\varepsilon)-5(4x+4y)=-8+8\varepsilon \\ 3i+j-5l &\geq& 3(5x-1+\varepsilon)+(5y-1+\varepsilon)-5(3x+y)=-4+4\varepsilon \\ i+3j-5k &\geq& (5y-1+\varepsilon)+3(5y-1+\varepsilon)-5(x+3y)=-4+4\varepsilon \end{array}$$

Since the left-hand sides are all integers, we deduce

$$\begin{array}{lclc} 4(i+j)-5(k+l) &\geq& -7 & (7) \\ 3i+j-5l &\geq& -3 & (8) \\ i+3j-5k &\geq& -3 & (9) \end{array}$$

We deduce from (7) that $4(i+j)-4(k+l) \geq -7$, so $\mu \geq -\frac{7}{4}$. Since $\mu$ is an integer, we must have $\mu \geq -1$. So the only thing we need to show is that $\mu\neq -1$. Suppose, by contradiction, that $\mu=(-1)$. Then $l=i+j-k+1$, and (8) and (9) can be rewritten

$$\begin{array}{lclc} -2i-4j+5k &\geq& 2 & (8') \\ -4i-2j+5l &\geq& 2 & (9') \end{array}$$

So $k$ and $l$ are both $\geq\frac{2}{5}$ ; we deduce

$$k\geq 1, l \geq 1 \tag{10}$$

since they are integers. Consider then the numbers

$$t_1=3i+j-5l+3, \ t_2=i+3j-5k+3, \ t_3=k-1, \ t_4=l-1$$

They are all nonnegative by (8), (9) and (10), but at the same time their sum is $4(i+j-(k+l))=-4$ and this is a contradiction, as wished.

• Yes, I also used that method and without loss of generality, assumed $5x \ge x+3y$. Then I had to check only the case when $5y \le y+3x$. It was tedious but I was able to prove it by seperating cases like this. But for the problem I suggested, it was just too tedious and too confusing so I just got stuck... That was the problem. Any suggestions about proving it? – Taxxi Nov 20 '13 at 18:15
• @TaxxiDriver Please see my update. – Ewan Delanoy Nov 22 '13 at 16:11
• Sorry for late replying I was sick. I checked your proof but it was actually not much better than just seperating some cases. I also thought about using your proof to prove the question I raised, but I still couldn't find a way to use it. I'm sad :( – Taxxi Nov 26 '13 at 4:10