1
$\begingroup$

$$x_1+x_2+x_3+x_4+x_5+x_6<538|x_i>0$$ The inequality is strict. Apparently, there are $\binom{537}{6}$ solutions to this after adding a new variable, $x_7$, that serves as a balance. Could someone walk me through this step-by-step? I realize that, if the inequality is strict, then $x_7 > 0$. I'm confused about the logic of counting the number of integer solutions.

$\endgroup$
2
  • 2
    $\begingroup$ Look up stars and bars and search for that on this site. $\endgroup$ – Ross Millikan Sep 8 '20 at 14:12
  • $\begingroup$ @RossMillikan Thanks for the guidance. I posted an answer $\endgroup$ – elbecker Sep 8 '20 at 14:26
1
$\begingroup$

Imagine 538 placeholder spaces to put an object. First add a balance variable $x_7$ to make an equality. $$x_1+x_2+x_3+x_4+x_5+x_6+x_7=538|x_7>0$$ The restriction on this variable is that $x_7>0$ for the equality and original strict inequality to hold true. Now distribute 1 object each to variables ${x_1...x_7}$ due to the restriction that $x_i>0$. This leaves 531 objects to distribute among 7 variables. There are 6 dividers to partition the set into 7 parts, which means there are $531+6=537$ placeholders for either a divider or an object. The answer is therefore $537\choose{6}$.

$\endgroup$
5
  • $\begingroup$ $x_7$ $\ge 0$, your answer is wrong $\endgroup$ – user800216 Sep 8 '20 at 16:33
  • $\begingroup$ @leonard I don't see what is wrong with it since a strict inequality has to be maintained. could you explain in more detail please $\endgroup$ – elbecker Sep 8 '20 at 16:38
  • $\begingroup$ i posted my answer .you can find what i meant. respects... $\endgroup$ – user800216 Sep 8 '20 at 16:46
  • $\begingroup$ what you missed is that $x_7$ does not have to be strict $\endgroup$ – user800216 Sep 8 '20 at 16:50
  • $\begingroup$ @elbecker: When you force $x_y$ to be positive and require that $x_1+\ldots+x_7=538$, you’re forcing $x_1+\ldots+x_6$ to be strictly less than $538$, thereby eliminating the solutions in which $x_1+\ldots+x_6=538$. You need to replace $538$ by $539$ if you want to require that $x_7$ be positive. Then your approach works and is at least arguably slightly simpler than elbecker’s. $\endgroup$ – Brian M. Scott Sep 8 '20 at 16:51

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.