$\begingroup$

Let $a,b,c$ be whole numbers so that $$1 \le a \le 3$$ $$2\le b \le4$$ $$3\le c \le5$$Find number of solutions of the equation, $a+b+c=10$. Note: Please use FPC/PnC to answer this instead of the binomial theorem

My Approach:

I treated this question as a variant of the normal Beggar's Method problem. so a,b,c are beggars and I need to distribute 10 coins among them. Since all the beggar's need to have a minimum amount of coins, I 'give' them those so the new question is, distributing 4 coins among 3 beggars such that:$$a \le 3$$ $$b \le4$$ $$c \le5$$

I couldn't solve this system of inequalities.

beggar's method

$\endgroup$ 2

2 Answers

$\begingroup$

That is correct. We need to find number of solutions to,$A + B + C = 4, $ where $A, B, C$ are non-negative numbers and $A \leq 2, B \leq 2, C \leq 2$. You can easily count case by case.

Alternatively, we could rewrite it as $A = 2 - x, B = 2 - y, C = 2 - z$ and find number of solutions to
$x + y + z = 2, x \leq 2, y \leq 2, z \leq 2$

Using stars and bars, we get ${4 \choose 2} = 6$ solutions.

Now coming back to counting number of solutions to $A + B + C = 4$, please see the cases below. Can you count number of solutions in each case?

• If $A = 0$, we have $B + C = 4$
• If $A = 1$, we have $B + C = 3$
• If $A = 2$, we have $B + C = 2$

$\endgroup$ 6 $\begingroup$

We can define the followings:

$$ \begin{align} x&=a\\ y&=b-1\\ z&=c-2 \end{align} $$

Our problem is now to find the number of positive integer solutions of $x+y+z=7$ in which all three are not greater than $3$. The solution without restriction is simple stars and bars:

$$ \binom{7-1}{3-1}=15 $$

The solution with one of $x,y,z$ exceeding $3$ is the solution of:

$$ \begin{align} x_{1}+y_{1}+z_{1}&=4\phantom{xx}x_{1},y_{1},z_{1}\in\mathbb{N}\\ x_{2}+y_{2}+z_{2}&=3\phantom{xx}x_{2},y_{2},z_{2}\in\{0,3\}\\ \\ x&=x_{1}+x_{2}\\ y&=y_{1}+y_{2}\\ z&=z_{1}+z_{2} \end{align} $$

The number of solutions can be calculated using stars and bars, permutation, and multiplication rule. So the answer to the original question is:

$$ \binom{7-1}{3-1}-3\cdot\binom{4-1}{3-1}=6 $$

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy