China Mathematical Competition

(1) Obviously the number of the values of $S$ is finite, so the maximum and minimum exist. Suppose $x_1+x_2+x_3+x_4+x_5=2006$ such that $S={\sum }_{1\le i<j\le 5}{x}_i{x}_j$ reaches the maximum, we must have $$|x_i-x_j|\le 1,(1\le i,j\le 5).$$ Otherwise, assume that this does not hold. Without loss of generality, suppose $x_1-x_2\ge 2$. Let $x_1^{\prime }=x_1-1$, $x_2^{\prime }=x_2+1$, $x_i^{\prime }=x_i$ ($i=3,4,5$). We have $$\begin{array}{rl}{x}_1^{\prime }+x_2^{\prime }+x_3^{\prime }+x_4^{\prime }+x_5^{\prime }& =x_1+x_2+x_3+x_4+x_5\\ & =2006,\end{array}$$ $$S=\sum _{1\le i<j\le 5}{x}_i{x}_j=x_1{x}_2+(x_1+x_2)(x_3+x_4+x_5)+x_3{x}_4+x_3{x}_5+x_4{x}_5,$$ $$S^{\prime }=x_1^{\prime }{x}_2^{\prime }+(x_1^{\prime }+x_2^{\prime })(x_3+x_4+x_5)+x_3{x}_4+x_3{x}_5+x_4{x}_5.$$ So $$S^{\prime }-S=x_1^{\prime }{x}_2^{\prime }-x_1{x}_2>0.$$ This contradicts the assumption that $S$ is the maximum. Therefore $|x_i-x_j|\le 1$ for $1\le i,j\le 5$. And it is easy to check that $S$ reaches the maximum when $$x_1=402,x_2=x_3=x_4=x_5=401.$$

(2) If we neglect the order in $x_1,x_2,x_3,x_4,x_5$, there could only be three cases: (a) $402,402,402,400,400$; (b) $402,402,401,401,400$; (c) $402,401,401,401,401$. That satisfy $x_1+x_2+x_3+x_4+x_5=2006$ and $|x_i-x_j|\le 2$. Cases (b) and (c) can be obtained from Case (a) by setting $x_i^{\prime }=x_i-1$, $x_j^{\prime }=x_j+1$. What we have done in (1) tells us that each step like this will make $S^{\prime }={\sum }_{1\le i<j\le 5}{x}_i^{\prime }{x}_j^{\prime }$ greater. So $S$ is the minimum in Case (a), i.e. $x_1=x_2=x_3=402$, $x_4=x_5=400$.