anonymous
  • anonymous
Determine the number of integer solutions to the inequality
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
What is the inequality?
anonymous
  • anonymous
\[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\]
ParthKohli
  • ParthKohli
Wow, this is a good question.

Looking for something else?

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

More answers

ParthKohli
  • ParthKohli
The number of nonnegative integral solutions to the equation:\[x_1+x_2 + \cdots + x_n = k\]is\[\binom{n+k-1}{k-1 }\]
ParthKohli
  • ParthKohli
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?
anonymous
  • anonymous
Yea!! 1< i <5 is the last subquestion
ParthKohli
  • ParthKohli
@oldrin.bataku just to party with a good question
ParthKohli
  • ParthKohli
\[N=\sum_{k=0}^{39}\binom{5+k-1}{k-1 }\]
ParthKohli
  • ParthKohli
The answer is an astonishing one: 7059052
anonymous
  • anonymous
But shouldnt the answear be 44 choose 39?
ParthKohli
  • ParthKohli
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.
anonymous
  • anonymous
Is the answear to xi>= -3 47 choose 38?
anonymous
  • anonymous
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..
ParthKohli
  • ParthKohli
That is a lot more interesting. Where did you get that figure?
anonymous
  • anonymous
I was just thinkin because it increases the intervall of combinationa with +3?
ParthKohli
  • ParthKohli
@oldrin.bataku plugging again
anonymous
  • anonymous
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)?
ParthKohli
  • ParthKohli
\[n = 5\]Number of nonnegative solutions to\[x_1 + x_2 + \cdots + x_n = k \]is\[\binom{n+k-1}{k-1}\]
ParthKohli
  • ParthKohli
do you understand why the above expression holds true?
anonymous
  • anonymous
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...
ParthKohli
  • ParthKohli
yay, she explained the stars-and-bars analogy to you.
Zarkon
  • Zarkon
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}\]
ParthKohli
  • ParthKohli
that's a grand mistake.
ParthKohli
  • ParthKohli
thanks for the catch.
anonymous
  • anonymous
@zarkon could you explain?
anonymous
  • anonymous
@Michele_Laino could you explain this a little further?
Michele_Laino
  • Michele_Laino
I'm very sorry, I'm not good with discrete mathematics
anonymous
  • anonymous
\[\sum_{k=0}^{39}\left(\begin{matrix}n+k-1 \\ n-1\end{matrix}\right)=1086008=\left(\begin{matrix}44 \\ 39\end{matrix}\right)\]
anonymous
  • anonymous
@Zarkon, @ParthKohli right? is \[\left(\begin{matrix}n+k-1 \\ n-1\end{matrix}\right)\] a known equation for this type of problems?
anonymous
  • anonymous
@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?
anonymous
  • anonymous
@oldrin.bataku
anonymous
  • anonymous
what is \[x_{i}\] exactly? is it the number of times the first value is choosen? i.e the startvalue ?
Zarkon
  • Zarkon
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\]
anonymous
  • anonymous
gj @Zarkon
Zarkon
  • Zarkon
\(x_i\) is the value of the \(i\)th number
anonymous
  • anonymous
Why do we let \[y _{i}=x _{i}+3\]
anonymous
  • anonymous
@Zarkon
anonymous
  • anonymous
@pate16 because it transforms the problem from \(x_i\ge-3\) into the standard stars-and-bars form in which \(x_i\ge0\)
anonymous
  • anonymous
er, the second should be \(y_i\ge0\)
anonymous
  • anonymous
ah, \[1\le i \le 5\]I see, hint for the last one?
anonymous
  • anonymous
oops, can you give me a hint for the last one I mean
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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
anonymous
  • anonymous
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
anonymous
  • anonymous
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}\)
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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
anonymous
  • anonymous
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
anonymous
  • anonymous
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$$
anonymous
  • anonymous
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 $$
anonymous
  • anonymous
How can I get the same answear as you but I dont use the slack variable?
anonymous
  • anonymous
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)\]
anonymous
  • anonymous
and the same for the first one to, but up to 39?
anonymous
  • anonymous
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}$$
anonymous
  • anonymous
I gotta go right now, but ill be back later so just finish what you are writing! thanks so much!
anonymous
  • anonymous
@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
anonymous
  • anonymous
that sum simplifies very cleanly by Pascal's identity, if you look: $$\binom44+\binom54+\binom64+\dots+\binom{43}4=\binom{44}5$$
anonymous
  • anonymous
@oldrin.bataku thanks so much! that is great!!!!

Looking for something else?

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