3
$\begingroup$

Find the number of integer solutions to the equation $x_1 + x_2 + x_3 = 28$, where $ 3 \leq x_1 \leq 9$, $0 \leq x_2 \leq 8$, and $7 \leq x_3 \leq 17$

I'm having problems with this question.

1) I first tried reducing the range of the variables to $ 0 \leq x_1 \leq 6$,$0 \leq x_2 \leq 8$ and $0 \leq x_3 \leq 10$.

2) That means I have to find the number of integer solutions for $x_1' + x_2' + x_3' = 18$ but I found I cannot reduce the ranges any further.

I have been told to use GPIE (General Principle of Inclusion and Exclusion) in this question but I would like to see other approaches as well.

The answer given is 28.

$\endgroup$
2
  • $\begingroup$ This might be helpful. $\endgroup$
    – taninamdar
    Sep 28, 2014 at 12:10
  • $\begingroup$ I don't think stars and bars can be used directly, right? That's why I tried reducing the ranges, but I'm still not able to use it. $\endgroup$
    – Malcolm X
    Sep 28, 2014 at 12:12

2 Answers 2

Reset to default
2
$\begingroup$

The equation

$$x_1 + x_2 + x_3 = 28$$

with the restrictions $3 \leq x_1 \leq 9$, $0 \leq x_2 \leq 8$, and $7 \leq x_3 \leq 17$ is equivalent to the equation

$$y_1 + y_2 + y_3 = 18$$

where $y_1 = x_1 - 3$, $y_2 = x_2$, and $y_3 = x_3 - 7$ with the restrictions $0 \leq y_1 \leq 6$, $0 \leq y_2 \leq 8$, and $0 \leq y_3 \leq 10$.

Let $z_1 = 6 - y_1$, $z_2 = 8 - y_2$, and $z_3 = 10 - y_3$. Then a solution to the equation $x_1 + x_2 + x_3 = 28$ with the given restrictions is equivalent to a solution of the equation

$$6 - z_1 + 8 - z_2 + 10 - z_3 = 18$$

in the non-negative integers. Simplifying yields

$$z_1 + z_2 + z_3 = 6$$

The number of solutions of this equation is equal to the number of ways two addition signs can be placed in a list of six ones. For instance, the list

$$+ 1 1 1 1 + 1 1$$

corresponds to the solution $z_1 = 0$, $z_2 = 4$, and $z_3 = 2$. Thus, we are selecting $2$ of the $6 + 2$ symbols to be addition signs, which can be done in

$$C(6 + 2, 2) = C(8, 2) = \frac{8!}{2!6!} = \frac{8 \cdot 7}{2 \cdot 1} = 28$$ ways.

$\endgroup$
0
$\begingroup$

Break it down into 7 cases, starting with $x_1'=0$ Then you only have one choice for the other two numbers, as they need to be maximal, so you have 1 choice. Each time $x_1'$ goes up by 1, you get one more potential choice for $x_2',x_3'$, so you get $1+2+3+4+5+6+7=28$ possibilities

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .