How many solutions possible for the equation $x_1+x_2+x_3+x_4=1000$ if all $x_1,x_2,x_3,x_4$ are non-negative integer and $\left| {{x_i} - {x_j}} \right| \in \left\{ {0,1} \right\}\text{ }\forall 1 \le i \ne j \le 4$. Thanks!

  • $\begingroup$ How many can you come up with? Can there be others? Can you prove that? $\endgroup$ – AakashM Sep 26 '12 at 16:00
  • $\begingroup$ You said inequality, but wrote =. Which is correct? $\endgroup$ – Ross Millikan Sep 26 '12 at 16:00
  • $\begingroup$ Looks like an equality, you have $x_1+x_2+x_3+x_4=1000$. Too simple. $\endgroup$ – André Nicolas Sep 26 '12 at 16:01

As Berci said, $x_1=x_2=x_3=x_4=250$ is a solution. Now let's prove there is no other solution satisfying the condition.

Suppose there is a different solution besides the above one, one of these four x's should be smaller than or larger than 250.

Without loss of generality, assume $x_1$ is smaller than 250. In order for their summation to be equal to 1000, at least one of the other three have to be bigger than 250. Therefore their absolute difference cannot be $\in \{0,1\}$ (one is smaller than 250, the other one is bigger than 250, their absolute difference is at least 2).

Now assume $x_1$ is bigger than 250, then at least one of the other three have to smaller than 250 in order for $\sum_{i=1}^{4} x_i = 1000$. And again their absolute difference is at least 2.

Conclusion, there can't be other solutions other than all x's being equal to 250.


So, if the distance of different $x_i$'s is really so much restricted, then the solutions don't have too much space to vary.

Clearly, $x_1=x_2=x_3=x_4=250$ is good.

Try to prove that there is nothing else. You can use that by hypothesis, the average of them must be $250$.

  • $\begingroup$ can you explain further? $\endgroup$ – Schwarz Sep 26 '12 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.