A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 one year ago
Determine the number of integer solutions to the inequality
anonymous
 one year ago
Determine the number of integer solutions to the inequality

This Question is Closed

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0What is the inequality?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.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\]

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2Wow, this is a good question.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2The number of nonnegative integral solutions to the equation:\[x_1+x_2 + \cdots + x_n = k\]is\[\binom{n+k1}{k1 }\]

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2The 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
 one year ago
Best ResponseYou've already chosen the best response.0Yea!! 1< i <5 is the last subquestion

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2@oldrin.bataku just to party with a good question

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2\[N=\sum_{k=0}^{39}\binom{5+k1}{k1 }\]

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2The answer is an astonishing one: 7059052

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0But shouldnt the answear be 44 choose 39?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2It'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
 one year ago
Best ResponseYou've already chosen the best response.0Is the answear to xi>= 3 47 choose 38?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Iam 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
 one year ago
Best ResponseYou've already chosen the best response.2That is a lot more interesting. Where did you get that figure?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I was just thinkin because it increases the intervall of combinationa with +3?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2@oldrin.bataku plugging again

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0But 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+k1) choose (k1)?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2\[n = 5\]Number of nonnegative solutions to\[x_1 + x_2 + \cdots + x_n = k \]is\[\binom{n+k1}{k1}\]

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2do you understand why the above expression holds true?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Not 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 k1 just represents the walls of the students...

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2yay, she explained the starsandbars analogy to you.

Zarkon
 one year ago
Best ResponseYou've already chosen the best response.1don't you want ... n=5 Number of nonnegative solutions to \[x_1+x_2+\cdots+x_n=k\] is \[{n+k1 \choose n1}\] instead of \[{n+k1 \choose k1}\]

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2that's a grand mistake.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.2thanks for the catch.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@zarkon could you explain?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@Michele_Laino could you explain this a little further?

Michele_Laino
 one year ago
Best ResponseYou've already chosen the best response.0I'm very sorry, I'm not good with discrete mathematics

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0\[\sum_{k=0}^{39}\left(\begin{matrix}n+k1 \\ n1\end{matrix}\right)=1086008=\left(\begin{matrix}44 \\ 39\end{matrix}\right)\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@Zarkon, @ParthKohli right? is \[\left(\begin{matrix}n+k1 \\ n1\end{matrix}\right)\] a known equation for this type of problems?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@Zarkon, @ParthKohli, if k starts from 3 it should be the same answear? cause the first \[\left(\begin{matrix}5+k1 \\ 51\end{matrix}\right)=\left(\begin{matrix}531 \\ 51\end{matrix}\right)=0\] \[\left(\begin{matrix}521 \\ 51\end{matrix}\right)=0\] \[\left(\begin{matrix}511 \\ 51\end{matrix}\right)=0\] and then it just starts over up to 39?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0what is \[x_{i}\] exactly? is it the number of times the first value is choosen? i.e the startvalue ?

Zarkon
 one year ago
Best ResponseYou've already chosen the best response.1for (2) let \[y_i=x_i+3\Rightarrow x_i=y_i3\] then \[x_1+x_2+x_3+x_4+x_5<40\] becomes \[y_13+y_23+y_33+y_43+y_53<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\]

Zarkon
 one year ago
Best ResponseYou've already chosen the best response.1\(x_i\) is the value of the \(i\)th number

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Why do we let \[y _{i}=x _{i}+3\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@pate16 because it transforms the problem from \(x_i\ge3\) into the standard starsandbars form in which \(x_i\ge0\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0er, the second should be \(y_i\ge0\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ah, \[1\le i \le 5\]I see, hint for the last one?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0oops, can you give me a hint for the last one I mean

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0basically, 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_i3\)) then they add up now to \(505\cdot3=40\) and each bin is an integer greater than or equal to 3, \(x_i\ge3\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0so 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
 one year ago
Best ResponseYou've already chosen the best response.0this 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 41 = 3 dividers amongst the 101 = 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{n1}{k1}\) 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+k1}{k1}\). 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_k1)=n+kk\\\implies \sum_{1\le i\le k}(y_k1)=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
 one year ago
Best ResponseYou've already chosen the best response.0here: $$\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+3k1}{k1}\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0oops 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
 one year ago
Best ResponseYou've already chosen the best response.0now, 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 starsandbars problem we had before; consider that if we deal with \(x_6'=x_61\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+61}6=\binom{44}6= 7059052 $$ @parthkoli

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0and 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
 one year ago
Best ResponseYou've already chosen the best response.0now, 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_61\) 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 starsandbars problem like before, so the answer is $$\binom{54+61}{61}=\binom{59}5=5006386$$

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0in the first problem i meant to write \(61\) in the binomial coefficient, so it's actually $$\binom{39+61}{61}=\binom{44}5= 1086008 $$

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0How can I get the same answear as you but I dont use the slack variable?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Im just summing them up in mathematica\[\sum_{k=0}^{54}\left(\begin{matrix}5+k1 \\ 51\end{matrix}\right)=\left(\begin{matrix}5+01 \\ 51\end{matrix}\right)+\left(\begin{matrix}5+11 \\ 51\end{matrix}\right)+...+\left(\begin{matrix}5+531 \\ 4\end{matrix}\right)\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0and the same for the first one to, but up to 39?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0so for standard starsandbars with nonempty bins, i.e. solutions to the equation \(x_1+\dots+x_k=n,\ x_k>0\) the expression is: $$\binom{n1}{k1}$$ 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+k1}{k1}$$ 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_kc\) where \(y_1+\dots+y_k=nck,\ y_k\ge 0\), which are counted using the expression above: $$\binom{nck+k1}{k1}=\binom{n+(1c)k1}{k1}$$note the \((1c)k\) reflects the fact that we can go straight to the first starsandbars case with nonnegative \(x_k\) immediately by using \(z_k=x_kc+1\) so that $$z_1+\dots+z_k=nck+k=n+(1c)k,\quad x_k>0$$ which is then given by the solution for *positive* (nonempty) \(z_k\), so: $$\binom{n+(1c)k1}{r1}$$

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I gotta go right now, but ill be back later so just finish what you are writing! thanks so much!

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@pate16 because of the recurrence relation between these binomial coefficients, also known as Pascal's identity ;) $$\binom{n}k=\binom{n1}{k1}+\binom{n1}k$$ one interpretation of the sum you have is that you're counting the cases where the slack is \(400=40\) so the solutions \(x_1+\dots+x_5=0\), then \(401=39\) so solutions to \(x_1+\dots+x_5=1\), ..., then \(40k\) so solutions to \(x_1+\dots+x_5=k\), ..., and finally where the slack is \(4039=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+51}{51}$$ 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 didand these are equivalent, which is what Pascal's identity does for us here

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0that sum simplifies very cleanly by Pascal's identity, if you look: $$\binom44+\binom54+\binom64+\dots+\binom{43}4=\binom{44}5$$

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@oldrin.bataku thanks so much! that is great!!!!
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.