4
$\begingroup$

So I have this question, and I know that I need to start off with downgrading $782$ to $762$ (to account for $x_4$ and $x_5$ being equal to $10$).

$x_1 +x_2+x_3+x_4+x_5 ≤ 782$

where $x_1,x_2 > 0$, $x_3 ≥ 0$

$x_4,x_5 \geq 10$.

How would I go about solving this using the combination formula after deflating $782$ to $762$?

$\endgroup$
3
$\begingroup$

Let $x_6 = 782 - (x_1 + x_2 + x_3 + x_4 + x_5)$. Then the inequality

$$x_1 + x_2 + x_3 + x_4 + x_5 \leq 782$$

becomes the equation

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

where $x_1, x_2$ are positive integers, $x_3, x_6$ are non-negative integers, and $x_4, x_5 \geq 10$. Let \begin{align*} y_1 & = x_1 - 1\\ y_2 & = x_1 - 1\\ y_3 & = x_3\\ y_4 & = x_4 - 10\\ y_5 & = x_5 - 10\\ y_6 & = x_6 \end{align*} Then each $y_i$, $1 \leq i \leq 6$, is a non-negative integer, and \begin{align*} y_1 + 1 + y_2 + 1 + y_3 + y_4 + 10 + y_5 + 10 + y_6 & = 782\\ y_1 + y_2 + y_3 + y_4 + y_5 + y_6 & = 760 \end{align*} The number of solutions of this equation in the non-negative integers is the number of ways five addition signs can be placed in a list of $760$ ones, which is $$\binom{760 + 5}{5} = \binom{765}{5}$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$y_1=x_1+1, y_2=x_2+1,y_3=x_3, y_4=x_4+10,y_5=x_5+10, y_6 \geq 0 \to (y_1+1)+(y_2+1)+y_3+(y_4+10)+(y_5+10)+y_6 = 782 \to y_1+y_2+y_3+y_4+y_5+y_6=762$. The number of solutions is:

$\binom{762+6-1}{6-1} = \binom{767}{5}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Be careful, you have $$y_1 + 1 + y_2 + 1 + y_3 + y_4 + 10 + y_5 + 10 = 762$$ which implies $$y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 760$$ Also, $y_1 = x_1 - 1$, $y_2 = x_2 - 1$, $y_4 = x_4 - 10$, and $y_5 = x_5 - 10$. $\endgroup$ – N. F. Taussig Jan 14 '15 at 23:04
1
$\begingroup$

Just as you already know, we first introduce the variables $y_1=x_1$, $y_2=x_2$, $y_3=x_3+1$, $y_4=x_4-9$ and $y_5=x_5-9$. Then your problem is equivalent to finding the number of integer solutions for the equation $$y_1+y_2+y_3+y_4+y_5\leq 765,$$ where $y_i\geq 1$.

The usual way of solving this kind of problem is the following: Suppose we have $765$ points in a line: $\bullet-\bullet-\cdots-\bullet$. You can think of a solution $y_1,\ldots,y_5$ as the following: take the set $A_1$ of the first $y_1$ points, then the set $A_2$ of the next $y_2$ points, $A_3$ the next $y_3$ points, same for $A_4$ and $A_5$: $$\underbrace{\bullet-\bullet-\cdots-\bullet}_{A_1}-\underbrace{\bullet-\cdots-\bullet}_{A_2}\cdots\underbrace{\bullet-\cdots-\bullet}_{A_5}-\bullet-\cdots-\bullet$$ so what really matters is the point at which each of the sets $A_1$, $A_2$, $A_3$, $A_4$ and $A_5$ finishes, that is, we have to calculate the number of choices of $5$ points among all those $765$ (and the order does not matter), which is $\binom{765}{5}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Another way to see this problem is dealing with each case separately:

  • before that we will modify the variable: $y_4 = x_4 -10 \geq 0 $ , $y_5 = x_5 -10 \geq 0 $ , $y_1=x_1 -1 \geq 0$, and $y_2 = x_2 -1 \geq 0$ our new system is $x_1 +x_2+x_3+y_4+y_5 \leq 760$

  • $y_1 +y_2+x_3+y_4+y_5 = 0\ $ ... , $\ y_1 +y_2+x_3+y_4+y_5 = k $ ... , $\ y_1 +y_2+x_3+y_4+y_5 = 760$ each case is disjoint the number of solutions is:

$N=\sum_{k=0}^{760} \binom{k-1+5}{5}$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Be careful: $x_1, x_2 > 0$. $\endgroup$ – N. F. Taussig Jan 14 '15 at 23:01
  • $\begingroup$ ops thats right, I need to modify the answer. Thank you. $\endgroup$ – SomeOne Jan 14 '15 at 23:02

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.