show this nice and hard inequality with $ \prod_{i=1}^{n}|x_{i}-y_{i}|I saw the following results in a book. The author said it was not difficult to prove how I felt it was difficult to prove, so I asked here. The result comes from a book that has no electronic version.Here's what I'm trying to prove.

let $x_{1}\ge x_{2}\ge\cdots\ge x_{n}\ge 0,y_{1}\ge y_{2}\ge\cdots\ge y_{n}\ge 0$,and such 
  $$\sum_{i=1}^{n}x_{i}=\sum_{i=1}^{n}y_{i}=n$$
  show that
  $$ \prod_{i=1}^{n}|x_{i}-y_{i}|<e^{\frac{n}{2}}$$

I try let$$A=\{i|x_{i}\ge y_{i}\},B=\{i|x_{i}<y_{i}\}$$
so 
$$\prod_{i=1}^{n}|x_{i}-y_{i}|=\prod_{i\in A}(x_{i}-y_{i})\prod_{i\in B}(y_{i}-x_{i})$$
and use AM-GM inequality we have
$$\prod_{i\in A}(x_{i}-y_{i})\le\left(\dfrac{\sum_{i\in A}(x_{i}-y_{i})}{|A|}\right)^{|A|}$$and 
$$\prod_{i\in B}(y_{i}-x_{i})\le\left(\dfrac{\sum_{i\in B}(y_{i}-x_{i})}{|B|}\right)^{|B|}$$
where $$|A|+|B|=n,\sum_{i\in B}x_{i}=n-\sum_{i\in A}x_{i},\sum_{i\in B}y_{i}=n-\sum_{i\in A}y_{i}$$
so let $$x=\sum_{i\in A}x_{i},y=\sum_{i\in A}y_{i},t=|A|$$
then we have
$$\prod_{i=1}^{n}|x_{i}-y_{i}|\le \left(\dfrac{x-y}{t}\right)^t\left(\dfrac{(n-y)-(n-x)}{n-t}\right)^{n-t}=\dfrac{(x-y)^n}{t^t(n-t)^{n-t}}$$
 A: Using your notation, one can work explicitly as follows. Let $s_A = \sum_{i \in A} |x_i - y_i|$ and $s_B = \sum_{i \in B} |x_i - y_i|$. Then 
$$\displaystyle s_A - s_B = \sum_{i \in A} (x_i - y_i) - \sum_{i \in B} (y_i - x_i) = n - n = 0,$$
hence $s_A = s_B = s$. Note that $s \leq n$ (this cannot be improved by much in general: say $x_1 = n, x_i = 0$ for $i = 2, \cdots, n$ and $y_i = 1$ for $i = 1, \cdots, n$). Thus by your AM-GM argument one gets 
$$\displaystyle \prod_{i = 1}^n |x_i - y_i| \leq s^n (n-x)^{x-n} x^{-x}$$
for $x = |A|$. The latter function can be optimized to give an upper bound of $(2s/n)^n$. This is slightly better than the bound given by Denis Serre, which takes the value $s = n$. 
Edit: I believe the following almost solves the problem. Note that the problem is trivial if $x_i = y_i$ for some $i$, so we assume that this is not the case. Without loss of generality, we suppose $x_1 > y_1$ and let $1, \cdots, m_1$ be the longest consecutive string containing 1 which lies in $A$. Then by AM-GM, we have
$$\displaystyle \prod_{i=1}^{m_1} (x_i - y_i) \leq \left(\frac{\sum_{i=1}^{m_1} (x_i - y_i)}{m_1}\right)^{m_1}.$$
Now replace $x_i, 1 \leq i \leq m_1$ by $u_1 = m_1^{-1} \sum_{i=1}^{m_1} x_i$ and likewise replace $y_i$ with the average of the first $m_1$ $y_i$'s. Note that the new sequence still satisfies the condition of the original problem, but the product is now larger. We do the same thing for the string $m_1 + 1, \cdots, m_2$, the longest consecutive string in $B$ containing $m_1 + 1$. Having done so, we now obtain a new sequence as follows:
$$u^{(1)} = u_1 = u_2 = \cdots = u_{m_1}, u^{(2)} = u_{m_1 + 1} = \cdots = u_{m_2}, \cdots,$$
$$v^{(1)} = v_1 = v_2 = \cdots = v_{m_1}, v^{(2)} = v_{m_1 + 1} = \cdots = v_{m_2}, \cdots$$
with the property that the sets of indices $A,B$ remain the same. Now we glue together consecutive blocks as follows. Take the first two blocks and replace each $v_i$ by the average of $v_1, \cdots, v_{m_2}$. Thus, we have replaced the values $v^{(1)}, v^{(2)}$ by their average. Indeed, this continues to preserve the conditions of the problem but enlarging each $|u_i - v_i|$. Do so with each pair of subsequent consecutive blocks. 
Now this part I am not sure how to write up properly, so I will just sketch the idea. One observes that for small $i$ the terms $x_i, y_i$ contribute disproportionately to the total sum (due to the monotonicity), so one wants to lower/narrow the left most blocks with large height; likewise the rightmost blocks with small height. Doing so one eventually concludes that the optimal configuration consists of just two blocks. Then our construction tells us that $y_1 = \cdots = y_n = 1$. Let $k = m_1$ (and $m_2 = n$). We can assume that $x_i = 0$ for $i > k$; otherwise the right blocks make the product smaller. Thus our construction yields that $x_1 = \cdots = x_k = n/k$. It then follows that our product is equal to
$$\displaystyle P(n,k) = \left(\frac{n}{k} - 1\right)^k.$$
The inequality $P(n,k) < e^{n/2}$ is equivalent to
$$\displaystyle \log\left(\frac{n}{k} - 1\right) < \frac{n}{2k}.$$
Put $s = n/k - 1$. We are then left to consider $\log(s) < (s+1)/2$. This inequality is immediately verified by calculus. 
A: Let me make the question more general: given a probability space $(X,d\mu)$ and two functions $f,g:X\rightarrow R_+$ such that $\int_Xfd\mu=\int_Xgd\mu=1$, find an upper bound of
$$\int_X\log|g-f|d\mu.$$
Because $\log$ is concave, the Jensen Inequality gives
$$\int_X\log|g-f|d\mu\le\log\int_X|g-f|d\mu=\log\left(2\int_X(g-f)_+d\mu\right)\le\log2.$$
Whence
$$\prod_1^n|y_i-x_i|\le2^n.$$
The bound $\log2$ is not optimal in this calculation. But it has a flaw: $X$ should be an interval and I should use the monotonicity of $f$ and $g$. This could be the reason of the better bound $e^{n/2}$.
A: Here's a proof I like but with an exercise left in it for the reader. Let $c_i = |x_i-y_i|$, let $A = \{i : x_i \geq y_i\}$ and $B$ the remainders, and let $c = \sum_{i \in A} c_i = \sum_{i \in B} c_i$. Under the constraints that $c_i \geq 0$ and these sums hold, we have
\begin{align}
  \prod_{i=1}^n |x_i - y_i|
  &=    \prod_{i\in A} c_i \prod_{j\in B} c_j  \\
  &\leq \left(\frac{c}{|A|}\right)^{|A|} \left(\frac{c}{|B|}\right)^{|B|}  \\
  &=     c^n \frac{1}{|A|^{|A|}} \frac{1}{(n-|A|)^{n-|A|}}  \\
  &=     \left(\frac{c}{n ~ \alpha^{\alpha} (1-\alpha)^{1-\alpha}}\right)^n
\end{align}
where $|A| = \alpha n$.
Now if we take the bound $c \leq n$ then we can optimize at $\alpha=1/2$ and recover the bound $2^n \approx e^{0.69 n}$. But I claim
Lemma. $c \leq \max\{|A|,|B|\}$.
(Since writing the rest of this proof I have not been able to prove the lemma. It follows from Iosof Pinelis' claim which has been posted meanwhile, so I leave it as an exercise -- I would love to have an elementary short proof. An equivalent statement is $\sum_{i=1}^n \min\{x_i,y_i\} \geq \min\{|A|,|B|\}$.)
Given the lemma, suppose WLOG that $\alpha \leq \frac{n}{2}$ so $c = (1-\alpha)n$, then we have
\begin{align}
  \left(\frac{c}{n ~ \alpha^{\alpha} (1-\alpha)^{1-\alpha}}\right)^n
  &=    \left(\left(\frac{1-\alpha}{\alpha}\right)^{\alpha}\right)^n  \\
  &=    \exp\left(n ~ \alpha \ln\frac{1-\alpha}{\alpha}\right) \\
  &\leq \exp\left(n ~ \alpha \ln\frac{1}{\alpha}\right)  \\
  &\leq e^{n/e} \\
  &\approx e^{0.37 n}
\end{align}
although bounding $1-\alpha$ by $1$ is clearly loose. Numerically it looks like $\approx e^{0.28 n}$.
