# Number of ways to divide $160$ into three parts

In how many ways can we divide $$160$$ into three parts, each with at least $$40$$ and at most $$60$$?

The amounts can only be integers. Please help me solve this, I don't really get exercises with at least and at most conditions.

• If you have no idea, why not try something easier first? What about dividing \$16 into three parts, each at least \$4 and at most \$6? Can you find the answer then? Can you do it in some systematic way that seems like it could be applied to the bigger problem? Mar 14, 2020 at 12:20 • Subtracting$40$from each, you can reduce the problem to finding three non-negative integers$a,b,c$which sum to$40$and which are each at most$20$. – lulu Mar 14, 2020 at 12:20 • The order of the parts doesn't matter here, right? Mar 14, 2020 at 12:22 • That is correct.$(50,50,60)$and$(50,60,50)\$ are two different solutions.
– lulu
Mar 14, 2020 at 12:27
• @lulu if it's correct and the order doesn't matter, then your example shows the same solution, doesn't it? Mar 14, 2020 at 12:29

SOLUTION:

This can be very easily solved by Partition method and then using generating function (other name: INTEGRAL EQUATION METHOD).

Let $$\displaystyle x+y+z = \160 \ \$$ as each gets atleast $$\40$$ so just divide $$\40$$ to each of them before hand.

Then the equation becomes $$\displaystyle a+b+c = \40 \ \$$ for some $$a,b,c$$.

Now we need to divide $$\20$$ among $$a,b,c$$ as at max each can get $$\60$$.

Thus By generating function or Integral equation method we can convert the following equation into this form :-

$$\displaystyle (1 + r^1 + r^2 + ... + r^{20})^3 = r^{40}$$

Where the coefficient of $$r^{40}$$ determines the number of possible solutions to the equation. By GP-summation we convert this into:

$$\displaystyle \frac {(1-r^{21})^3}{(1-r)^3} = r^{40} \implies (1-r^{21})^3(1-r)^{-3} = r^{40}$$

Now if we ibserve it then we can see that the terms that matter to us in $$({1-r^{21}})^3$$ is just $$({1-3r^{21}})$$, as rest of the terms have exponents greater than $$40$$.

So, we get the coefficient of $$r^{40}$$ by $$\displaystyle \binom {40 + 3-1}{3-1} - 3 \times \binom {19 + 3-1}{3-1}$$, thus the answer is:

$$\displaystyle \binom {42}{2} - 3\binom {21}{2} = 231 .$$

So first, because each number is at least $$40$$, so we may minus 40 from each number. So the remaining part is how to divide $$40$$ into $$3$$ parts, each part is at most $$20$$.

We now consider $$a,b,c$$ with $$a+b+c=40$$, then set $$x=20-a, y=20-b,z=20-c$$, so $$x+y+z$$=$$20$$ and $$x,y,z$$ is at least $$0$$.

Now it is clear that the number of triples $$(x,y,z)$$ is the number of $$(a,b,c).$$

We may play the bar and star here.

So let there be 20 stars on a row and we must place 2 bars to separate the three parts.

If all 3 numbers are positive then there are $$\displaystyle \binom{19}{2} = 171$$ triples

If one of the three number is $$0$$ then there are $$\displaystyle 3\times \binom{19}{1} =57$$ triples.

If one of the thee numbe is $$20$$ then there are $$3$$ triples.

In total there are $$231$$ triples.

The condition:

$$x'+y'+z'=160, \ 40\le x',y',z'\le 60$$

...is equivalent to:

$$x+y+z=40, \ 0\le x,y,z\le 20 \tag{1}$$

...with:

$$x'=x+40,\ y'=y+40,\ z'=z+40$$

So the number of soulutions that you are looking for is identical to the number of solutions of (1). Notice that we have decide about values of $$x,y$$. The value of $$z$$ can be calculated from (1).

$$x=0 \implies y=20\tag{2-0}$$ $$x=1 \implies y \in \{20, 19\}\tag{2-1}$$ $$x=2 \implies y \in \{20, 19, 18\}\tag{2-2}$$ $$x=3 \implies y \in \{20, 19, 18, 17\}\tag{2-3}$$ $$\dots$$ $$x=20 \implies y \in \{20, 19, 18, 17,\dots,0\}\tag{2-20}$$

So you have 1 solution from (2-0), 2 solutions from (2-1), 3 solutions from (2-2).... and 21 solution from (2-20). The total number of solutions is:

$$1+2+3+...+21=231$$

• This method of presenting is a little bit hard to follow don't you see? Mar 14, 2020 at 15:49

All of the parts are greater than or equal to $$40$$,

So the sum will be at least $$120$$.

Now the remaining $$40$$ needs to be partitioned into $$3$$ groups $$A,B,C$$ so that none of the groups have more than $$20$$

The total ways to do this without the $$20$$ limit restriction is:

$$A+B+C=40$$, hence $$\binom{42}{2}$$ ways.

Now we have to subtract ways in which $$1$$ group has more than $$20$$

Lets say that $$A \gt 20$$

So $$B+C \lt 40-20$$, or in other words, $$B+C+D*=19$$

This can be done in: $$\binom{21}{2}$$ ways

Now any of $$A,B,C$$ could have been $$\gt 20$$

$$3\cdot \binom{21}{2}$$

And finally,

$$\binom{42}{2}-3\cdot \binom{21}{2}$$

*$$D$$ was added as another variable to account for the fact that if $$B+C=18$$, $$D=1$$, similarly if $$B+C=12$$, $$D=7$$ and so on