Proving Inequality with the Greatest Integer Function

Question

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.

Answer 1

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

Answer 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.