A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Determine the number of integer solutions to the inequality

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    What is the inequality?

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[x _{1} + x _{2} + x _{3} + x _{4} + x _{5} <40\] \[1. x _{i} \ge 0\] \[2.x _{i} \ge -3\] \[1\le i \le 5\]

  3. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Wow, this is a good question.

  4. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    The number of nonnegative integral solutions to the equation:\[x_1+x_2 + \cdots + x_n = k\]is\[\binom{n+k-1}{k-1 }\]

  5. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    The inequality is \(x_1 + x_2 + x_3 + x_4 + x_5 < 40\) and not \(x_1 + x_2 + \cdots + x_i\) where \(1 \le i \le 5\) right?

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yea!! 1< i <5 is the last subquestion

  7. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    @oldrin.bataku just to party with a good question

  8. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    \[N=\sum_{k=0}^{39}\binom{5+k-1}{k-1 }\]

  9. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    The answer is an astonishing one: 7059052

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But shouldnt the answear be 44 choose 39?

  11. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    It's great that you're following me. The answer is no. Note that we want to find the number of solutions to the inequality \(\rm something < 40\) which boils down to adding the solutions of the equalities \(\rm something = 1, 2, \cdots, 39\). The combination expression gives the number of solutions to equalities, not inequalities. So yeah.

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Is the answear to xi>= -3 47 choose 38?

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Iam following I think, But I still couldnt explain it good to my frienda or teacher, I dont know how to write it down on my paper..

  14. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    That is a lot more interesting. Where did you get that figure?

  15. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I was just thinkin because it increases the intervall of combinationa with +3?

  16. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    @oldrin.bataku plugging again

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But in the sum you did upthere, sorry fr not writing in latex im on my phone right now... but in the sum why is it (5+k-1) choose (k-1)?

  18. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    \[n = 5\]Number of nonnegative solutions to\[x_1 + x_2 + \cdots + x_n = k \]is\[\binom{n+k-1}{k-1}\]

  19. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    do you understand why the above expression holds true?

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Not reqlly, the only thing our teacher did with this is some kind of cinnamon buns example with four students and 12 buns, x1+x2+x3+x4=12 and the k-1 just represents the walls of the students...

  21. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    yay, she explained the stars-and-bars analogy to you.

  22. Zarkon
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    don't you want ... n=5 Number of nonnegative solutions to \[x_1+x_2+\cdots+x_n=k\] is \[{n+k-1 \choose n-1}\] instead of \[{n+k-1 \choose k-1}\]

  23. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    that's a grand mistake.

  24. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    thanks for the catch.

  25. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @zarkon could you explain?

  26. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Michele_Laino could you explain this a little further?

  27. Michele_Laino
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm very sorry, I'm not good with discrete mathematics

  28. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[\sum_{k=0}^{39}\left(\begin{matrix}n+k-1 \\ n-1\end{matrix}\right)=1086008=\left(\begin{matrix}44 \\ 39\end{matrix}\right)\]

  29. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Zarkon, @ParthKohli right? is \[\left(\begin{matrix}n+k-1 \\ n-1\end{matrix}\right)\] a known equation for this type of problems?

  30. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Zarkon, @ParthKohli, if k starts from -3 it should be the same answear? cause the first \[\left(\begin{matrix}5+k-1 \\ 5-1\end{matrix}\right)=\left(\begin{matrix}5-3-1 \\ 5-1\end{matrix}\right)=0\] \[\left(\begin{matrix}5-2-1 \\ 5-1\end{matrix}\right)=0\] \[\left(\begin{matrix}5-1-1 \\ 5-1\end{matrix}\right)=0\] and then it just starts over up to 39?

  31. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @oldrin.bataku

  32. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    what is \[x_{i}\] exactly? is it the number of times the first value is choosen? i.e the startvalue ?

  33. Zarkon
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    for (2) let \[y_i=x_i+3\Rightarrow x_i=y_i-3\] then \[x_1+x_2+x_3+x_4+x_5<40\] becomes \[y_1-3+y_2-3+y_3-3+y_4-3+y_5-3<40\] \[y_1+y_2+y_3+y_4+y_5<40+15\] \[y_1+y_2+y_3+y_4+y_5<55\] and the \[y_i\ge 0\]

  34. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    gj @Zarkon

  35. Zarkon
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \(x_i\) is the value of the \(i\)th number

  36. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Why do we let \[y _{i}=x _{i}+3\]

  37. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Zarkon

  38. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @pate16 because it transforms the problem from \(x_i\ge-3\) into the standard stars-and-bars form in which \(x_i\ge0\)

  39. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    er, the second should be \(y_i\ge0\)

  40. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ah, \[1\le i \le 5\]I see, hint for the last one?

  41. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oops, can you give me a hint for the last one I mean

  42. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    basically, consider the problem where we partition the \(55\) into 5 nonnegative integers \(y_1,\dots,y_5\). if we afterward throw away 3 from each 'bin' (subtract 3 from each of those integer parts, so \(x_i=y_i-3\)) then they add up now to \(50-5\cdot3=40\) and each bin is an integer greater than or equal to -3, \(x_i\ge-3\)

  43. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so counting the nonnegative partitions of \(40+5\cdot3=55\) is equivalent to countign the integer partitions of \(40\) with the requirement that each is greater than or equal to \(-3\) rather than merely nonnegative

  44. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    this is a generalization of the method we use when taking stars and bars from positive integers to nonnegative integers. the original method of stars and bars involves n indistinguishable items (stars) that we want to distribute amongst k distinct bins such that no bin is nonnegative (i.e. number of *positive* solutions to \(\sum_{1\le i\le k} x_i=n\)). suppose we have 10 stars: * * * * * * * * * * now, if we had, say, 4 bins, then we want to find the number of ways to place 4-1 = 3 dividers amongst the 10-1 = 9 spaces between stars: * * * * * * * * * * ^ ^ ^ ^ ^ ^ ^ ^ ^ there are clearly \(\binom{9}3\) such ways to place the three dividers so that we get 4 bins of distinct size. in general, for n stars and k bins, the above reasoning gives \(\binom{n-1}{k-1}\) possible partitions, or positive integer solutions to \(\sum_{1\le i\le k}x_i=n\). to generalize this to *nonnegative* partitions, i.e. cases where we could have empty bins, suppose we instead add \(k\) new stars and then find the positive integer partitions of these total \(n+k\) stars amongst \(k\) bins, and then remove one star from each bin. this sets up a bijection between the partitions of \(n+k\) indistinguishable stars amongst \(k\) distinct nonempty bins and partitions of of \(n\) indistinguishable stars amongst \(k\) distinct *possibly empty* bins, so it follows that the expression here gives \(\binom{n+k-1}{k-1}\). in terms of solutions to \(\sum_{1\le i\le k}x_k=n\) we have that the solutions to \(\sum_{1\le i\le k}x_k=n\) with \(x_k\ge0\) is equivalent to the problem of \(\sum_{1\le i\le k}y_k=n+k\) with \(y_k\ge1\), since we can simply subtract 1 from each of the \(y_i\) to give: $$\sum_{1\le i\le k}y_k=n+k\\\implies \sum_{1\le i\le k}(y_k-1)=n+k-k\\\implies \sum_{1\le i\le k}(y_k-1)=n$$ or add 1 to each of the \(x_k\) in the corresponding problem so that every solution of one corresponds to a unique solution of the other in a similar way, we can extend the above reasoning to bins that contain 'negative' numbers of stars simply by *adding* or *subtracting* more than 1 item per bin

  45. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    here: $$\sum_{1\le i\le k}x_k=n,\quad x_k\ge -3$$ consider if we add \(3\) to each solution, we get: $$\sum_{1\le i\le k}(x_k+3)=n+3k$$now these \(x_k+3\) correspond to a perfectly good solution \(y_k\) to the complementary problem \(\sum_{1\le i\le k}y_k=n+3k,\ y_k\ge 0\). so counting the solutions to the first problem is the 'same' combinatorially to counting solutions to the bottom problem, and we just showed in the previous post that the second problem is just \(\binom{n+3k-1}{k-1}\)

  46. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oops I meant \(x_i,y_i\) for \(1\le i\le k\) in the summations of the previous problems, not specifically \(x_k,y_k\)

  47. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    now, the trick in this problem to *not* have to add all the solutions from \(1\) to \(40\) has multiple interpretations; in one, you're using the fact that these binomial coefficients (really encoding *multiset* numbers) satisfy a recurrence relation which lets us condense the big ugly sum. in another interpretation, we're introducing a 'slack' variable \(x_6\) to quantify the difference between \(x_1+\dots+x_5\) and \(40\), and requiring \(x_k>0\). observe: $$x_1+x_2+x_3+x_4+x_5+x_6=40\\x_1,x_2,x_3,x_4,x_5\ge0\\x_6>0$$ now, we'd really like to have all of our variables satisfy the same constraint to reduce it to the easy stars-and-bars problem we had before; consider that if we deal with \(x_6'=x_6-1\ge0\) instead, and then add a star for \(x_6\) specifically, we get consistent requirements on all of variables so \(x_1,\dots,x_5,x_6'\ge 0\) transforming our problem into: $$x_1+x_2+x_3+x_4+x_5+x_6'+1=40\\\implies x_1+x_2+x_3+x_4+x_5+x_6'=39$$ now, how many nonnegative partitions of \(39\) into \(6\) bins are there? simple! $$\binom{39+6-1}6=\binom{44}6= 7059052 $$ @parthkoli

  48. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and this is the same concept of a 'slack' variable that comes up in optimization when transforming inequality constraints into equations, such as in linear programming problems: https://en.wikipedia.org/wiki/Slack_variable

  49. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    now, let's tackle the next one. we have: $$x_1+x_2+x_3+x_4+x_5<40,\quad x_i\ge -3$$ if we instead look at waht this problem spells for \(y_i=x_i+3\) we see: $$y_1+y_2+y_3+y_4+y_5<40+3\cdot5=55,\quad y_i\ge 0$$now, we introduce another slack variable, here \(y_i\), to compensate for the difference of \(y_1+\dots+y_5\) and \(55\): $$y_1+y_2+y_3+y_4+y_5+y_6=55,\quad y_1,y_2,y_3,y_4,y_5\ge 0,\quad y_6>0$$just as before, we can 'set aside' one star for \(y_6\) to guarantee it stays positive and is never zero by looking instead at \(y_6'=y_6-1\) and requiring \(y_6'\ge 0\) so $$y_1+y_2+y_3+y_4+y_5+y_6'+1=55,\quad y_1,\dots,y_5,y_6'\ge 0\\\implies y_1+y_2+y_3+y_4+y_5+y_6'=54$$ and this is just an easy standard stars-and-bars problem like before, so the answer is $$\binom{54+6-1}{6-1}=\binom{59}5=5006386$$

  50. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    in the first problem i meant to write \(6-1\) in the binomial coefficient, so it's actually $$\binom{39+6-1}{6-1}=\binom{44}5= 1086008 $$

  51. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How can I get the same answear as you but I dont use the slack variable?

  52. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Im just summing them up in mathematica\[\sum_{k=0}^{54}\left(\begin{matrix}5+k-1 \\ 5-1\end{matrix}\right)=\left(\begin{matrix}5+0-1 \\ 5-1\end{matrix}\right)+\left(\begin{matrix}5+1-1 \\ 5-1\end{matrix}\right)+...+\left(\begin{matrix}5+53-1 \\ 4\end{matrix}\right)\]

  53. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and the same for the first one to, but up to 39?

  54. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so for standard stars-and-bars with nonempty bins, i.e. solutions to the equation \(x_1+\dots+x_k=n,\ x_k>0\) the expression is: $$\binom{n-1}{k-1}$$ if we instead allow empty bins, i.e. \(x_1+\dots+x_k=n,\ x_k\ge 0\) we basically add one star for each bin (so \(y_i=x_i+1, n\to n+k\)) and then use the previous expression for nonempty solutions to solve \(y_1+\dots+y_k=n+k,\ y_k>0\), and then remove one from each bin afterward to give us a solution: $$\binom{n+k-1}{k-1}$$ more generally, if we have \(x_1+\dots+x_k=n,\ x_k\ge c\) then we can use an analogous trick to the previous case (nonnegative) by instead looking at solutions to the problem with \(y_i=x_k-c\) where \(y_1+\dots+y_k=n-ck,\ y_k\ge 0\), which are counted using the expression above: $$\binom{n-ck+k-1}{k-1}=\binom{n+(1-c)k-1}{k-1}$$note the \((1-c)k\) reflects the fact that we can go straight to the first stars-and-bars case with nonnegative \(x_k\) immediately by using \(z_k=x_k-c+1\) so that $$z_1+\dots+z_k=n-ck+k=n+(1-c)k,\quad x_k>0$$ which is then given by the solution for *positive* (nonempty) \(z_k\), so: $$\binom{n+(1-c)k-1}{r-1}$$

  55. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I gotta go right now, but ill be back later so just finish what you are writing! thanks so much!

  56. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @pate16 because of the recurrence relation between these binomial coefficients, also known as Pascal's identity ;-) $$\binom{n}k=\binom{n-1}{k-1}+\binom{n-1}k$$ one interpretation of the sum you have is that you're counting the cases where the slack is \(40-0=40\) so the solutions \(x_1+\dots+x_5=0\), then \(40-1=39\) so solutions to \(x_1+\dots+x_5=1\), ..., then \(40-k\) so solutions to \(x_1+\dots+x_5=k\), ..., and finally where the slack is \(40-39=1\) so \(x_1+\dots+x_5=39\). the sum total of these solutions for the possible slack values of \(1\) to \(40\) is written: $$\sum_{k=0}^{39}\binom{k+5-1}{5-1}$$ alternatively, we can count all the possible solutions to \(x_1+\dots+x_5+\underbrace{x_6}_{\text{slack}}=40\) for \(x_1,\dots,x_5\ge 0\) and a positive slack \(x_6>0\) (to ensure the inequality is strict and we don't include \(x_1+\dots+x_5=40\), only up to \(39\)) all at once, which is what i did--and these are equivalent, which is what Pascal's identity does for us here

  57. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that sum simplifies very cleanly by Pascal's identity, if you look: $$\binom44+\binom54+\binom64+\dots+\binom{43}4=\binom{44}5$$

  58. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @oldrin.bataku thanks so much! that is great!!!!

  59. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.