GATE Overflow Test Series | Discrete Mathematics | Test 2 | Question: 15

Question

Number of positive integer solutions to the equation $4x+y+z = 21$ is $\_\_\_\_$

Comments

generating function is :

$\frac{1}{1-x^{4}}\times \frac{1}{{(1-x)}^{2}}$

 

find the coefficient of $x^{15}$

---

@Shaik Masthan

sir can you find some resources to learn to solve by this way? i mean how to create the generating function for this equation?

---

https://gateoverflow.in/300829/Madeeasy-test-series

https://gateoverflow.in/39714/Gate-cse-2016-set-1-question-27  ( i mentioned one pdf in my answer)

---

Thanks sir

Answer 1

$4x + y + z = 21,\qquad x,y,z > 0$

$\implies 4x + y + z = 15, \qquad x,y,z \geq 0$

Here, the possible values of $4x$ are $0,4,8,12.$ For each of these possible values we can find the number of possible values of $y+z$ as follows

1. $y+z = 15.$

This can be solved by stars-and-bars technique with $15$ stars and $1$ bar giving ${}^{16}C_1 = 16$ ways.

2.$y + z = 11.$

$12$ ways

3. $y+z = 7.$

$8$ ways

4. $y+z = 3.$

$4$ ways

So, totally we get $16+12+8+4 = 40$ ways.

Comments

values of x, y ,z here are >0 but to apply the stars and bars technique we should use >=0

so if we take x1+x2 = 20 where x1>=1, x2>=1

x1+x2=20, x1-1>=0 and x2-1>=0

x1-1 + x2-1 = 20-2

taking x1-1 = y1 and x2-1 = y2

y1 + y2 = 18 where y1,y2>=0

---

@psrock541, We can get the answer without making x,y,z >= 0.

i.e if 4x + y + z = 21 where x,y,z > 0

Then possible values of 4x are 4,8,12,16.

1.4x = 4 → y + z = 17, Now we have to apply one bar between 16 places. So we get 16C1=16 ways.

2.4x = 8 → y + z = 13  => Number of ways = 12.

Same logic for 4x = 12  => Number of ways = 8

and for 4x = 16 => Number of ways = 4.

Total ways = 16 + 12 + 8 + 4 = 40.

---

If here x is 5 then what is  the issues in this question  we have to take x from 1 to 5 ?

 

Answer 2

Here Number of positive integer solutions is asked. So, the minimum values of x,y,z must be greater than or equal to 1.

The possible values of x are 1,2,3,4.

Note:

“The value of x cannot be equal to 5 because if x=5 the given equation becomes 4(5)+y+z=21 => y+z =1 (in order to satisfy this equation either y or z must be 0(not a positive integer solution).”

So, by now you are convinced that x can take values 1,2,3,4.

 

if x=1,

the given equation becomes 4(1)+y+z=21 => y+z=17

Now the possible values y and z such that y+z = 17 is

(1,16),(2,15),(3,14),(4,13),(5,12),(6,11),(7,10),(8,9) = 8 ways.

The above, each pair of values for y and z can be allocated in 2 ways so the number of solutions

= 2*8 =16 ways.

 

if x=2,

the given equation becomes 4(2)+y+z=21 => y+z=13

Now the possible values y and z such that y+z = 13 is

(1,12),(2,11),(3,10),(4,9),(5,8),(6,7) = 6 ways.

The above, each pair of values for y and z can be allocated in 2 ways so the number of solutions

= 2*6 =12 ways.

 

 

if x=3,

the given equation becomes 4(3)+y+z=21 => y+z=9

Now the possible values y and z such that y+z = 13 is

(1,8),(2,7),(3,6),(4,5) = 4 ways.

The above, each pair of values for y and z can be allocated in 2 ways so the number of solutions

= 2*4 =8 ways.

 

 

if x=4,

the given equation becomes 4(4)+y+z=21 => y+z=5

Now the possible values y and z such that y+z = 13 is (1,4),(2,3) = 2 ways.

The above, each pair of values for y and z can be allocated in 2 ways so the number of solutions = 2*2 =4 ways.

 

Adding the above values when x=1,2,3,4 is 16+12+8+4 = 40.