3
$\begingroup$

I just had this question in an exam and was unsure how to complete some parts using the Stars and Bars method.

Problem as follows:

How many solutions has the equation:

$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 78$

If $x_1, x_2, x_3, x_4, x_5, x_6$ are non-negative integers and:

a) there are no further restrictions

b) all of $x_1, x_2, x_3, x_4, x_5, x_6$ are odd numbers

c) at least one of $x_1, x_2, x_3, x_4, x_5, x_6$ is greater than or equal to 30.


My attempts if they are worth anything, I believe I'm not familar enough with the method which lead to me misusing it:

a) This one was straight foward, I got $\binom{83}{5}$, by defintion of the method.

b) I'm certain I got this part wrong. I used my result from part (a), and minused it by the number of solutions where $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 78$ is even. I.e. where we $x_1, x_2, x_3, x_4, x_5, x_6$ represent two stars such that $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 39$.

So the final calculation was $\binom{83}{5}$ - $\binom{44}{5}$, but this doesn't make numerical sense. $\ddot\frown$

c) Not too sure about this one either. I tried 'reserving' 30 stars such that $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 48$, so $\binom{53}{5}$.

Similarly for the other case where there is some $x_i$ and $x_j$ are both greater than 30 so I 'reserve' 60 stars such that $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 18$ so $\binom{18}{5}$.

Then I added the two together such that $\binom{18}{5} + \binom{53}{5} $

$\endgroup$
  • 1
    $\begingroup$ In c) the reserved $30$ can be added to $6$ candidates, giving a factor $6$ for the number of possibilities. Secondly the twice reserved $30$ gives likewise a factor $\binom{6}{2}=15$. Thirdly (in my view the most tricky) there is a double counting. A possibility where $30$ is added can be the same as one where $30$ is added twice. $\endgroup$ – drhab Nov 18 '14 at 10:56
1
$\begingroup$

Hint on b)

Find the number of solutions of $z_{1}+\cdots+z_{6}=36$ under no restrictions.

This comes to the same as finding the number of solutions of $y_{1}+\cdots+y_{6}=72$ under condition that all numbers are even.

And on its turn it comes to the same as finding the number of solutions of $x_{1}+\cdots+x_{6}=78$ under condition that all numbers are odd.

This by taking $y_i=2z_i$ and $x_{i}=y_{i}+1=2z_{i}+1$.

$\endgroup$

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.