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$.

combinationscombinatoricspermutations

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

Best Answer

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$
Related Question