Not as easy as it looks

Find the number of non-negative integer solutions of

3 x + y + z = 24. 3x +y + z = 24.


The answer is 117.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

The problem can be solved easily using generating functions . The generating function associated with the term 3 x 3x is 1 + x 3 + x 6 + . . . + x 24 = 1 1 x 3 1+x^3+x^6+...+x^{24}= \frac{1}{1-x^3} , while y , z y,z have correspond to the same polynomial 1 1 x \frac{1}{1-x} . Solving the question now comes down to finding the coefficient of x 24 x^{24} in the expansion of 1 1 x 3 ( 1 1 x ) 2 \frac{1}{1-x^3} \cdot (\frac{1}{1-x})^2 , which can be done using (for example) Wolfram Alpha leading to 117 117 .

Doing the calculation by hand is not difficult:

1 ( 1 x ) 2 = k = 0 ( 2 + k 1 1 ) x k = 1 + 2 x + 3 x 2 + 4 x 3 + + 25 x 24 \frac{1}{(1-x)^2} = \sum_{k=0}^{\infty} {2+k-1 \choose 1} \cdot x^k = 1+2x+3x^2+4x^3+\dots+25x^{24}

from the negative binomial series . We have to evaluate the coefficient of x 24 x^{24} in the product (ignoring higher order terms) ( 1 + x 3 + x 6 + + x 24 ) ( 1 + 2 x + 3 x 2 + + 25 x 24 ) (1+x^3+x^6+\dots +x^{24}) \cdot (1+2x+3x^2+\dots+25x^{24}) which is equivalent to evaluating the sum 25 + 22 + 19 + 16 + + 1 = 9 + 3 ( 1 + 2 + + 8 ) = 9 + 3 8 9 2 = 117 25+22+19+16+\dots+1= 9+3\cdot(1+2+\cdot+8)=9+3\cdot \frac{8\cdot9}{2}=117

wait is there any way of getting 117 using this method without using a calculator? or a super long process?

A Former Brilliant Member - 2 years, 10 months ago

Log in to reply

I thought about it and edited the solution with a nice way to do it! Thank you for the stimulating question.

Gabriele Manganelli - 2 years, 10 months ago

Since x x must be an integer, 3 x 3x must also be an integer. Between 0 0 and 24 24 these multiples k k are 0 , 3 , 6 , 9 , 12 , 15 , 18 , 21 , 24 0, 3, 6, 9, 12, 15, 18, 21, 24 . If anyone knows a more efficient way, please let me know. I, being the lazy person, simply counted the number of solutions for each y + z = 24 k y+z=24-k using stars and bars . Adding them together gives us 117 117 .

The general formula for the number of solutions to an equation of the kind r x 1 + x 2 + . . . + x n = k r rx_1+x_2+...+x_n=kr is i = 0 k ( r ( k i ) + n 2 n 2 ) \displaystyle\sum_{i=0}^{k} \binom{r(k-i)+n-2}{n-2} . Can anyone give a proof?

@Brian Charlesworth How could this be done quicker?


Since I'm currently studying Python, here's my Python code:

            n=0

            for x in range(9):

            for y in range(25):

            for z in range(25):

            if x*3+y+z == 24:

            n += 1

        print n

117 \color{#3D99F6}{117}

if 3x+4y+5z=100 if x,y,z non negative integer then how many solution of this equation? plz solve this

Atique Shahriar - 3 years ago

Log in to reply

First see that 'x' is divisible by both 4 and 5,'y' is divisible by 5 and 'z' is divisible by 4(analyzing the equation).So we can write the equation as 60a+20b+20c=100 for some a,b,c>=0.It is obvious that 0,1 are the only possible values for a.Now let some of the values of a,b,c be 0 and it is not difficult to see that the solutions are the following: (0,0,20),(0,25,0),(20,10,0),(20,0,8),(0,5,16),(0,10,12),(0,15,8),(0,20,4),(20,5,4) (the strategy was to let one of the values of a,b,c be 0 and then finding the solution for the other two).So there are total 9 solutions.

Akash Hossain - 3 years ago

Log in to reply

See Robert Zwart's comment above............

Aaghaz Mahajan - 2 years, 10 months ago

Using the appropriate generating function 1 / ( (1-x^3) * (1-x^4) * (1-x^5) ) the coëfficiënt of x^100 in the related series expansion is 94, so there are 94 solutions.

Here all the 94 {x,y,z} triples are enumerated: {0,0,20},{0,5,16},{0,10,12},{0,15,8},{0,20,4},{0,25,0},{1,3,17},{1,8,13},{1,13,9},{1,18,5},{1,23,1},{2,1,18},{2,6,14},{2,11,10},{2,16,6},{2,21,2},{3,4,15},{3,9,11},{3,14,7},{3,19,3},{4,2,16},{4,7,12},{4,12,8},{4,17,4},{4,22,0},{5,0,17},{5,5,13},{5,10,9},{5,15,5},{5,20,1},{6,3,14},{6,8,10},{6,13,6},{6,18,2},{7,1,15},{7,6,11},{7,11,7},{7,16,3},{8,4,12},{8,9,8},{8,14,4},{8,19,0},{9,2,13},{9,7,9},{9,12,5},{9,17,1},{10,0,14},{10,5,10},{10,10,6},{10,15,2},{11,3,11},{11,8,7},{11,13,3},{12,1,12},{12,6,8},{12,11,4},{12,16,0},{13,4,9},{13,9,5},{13,14,1},{14,2,10},{14,7,6},{14,12,2},{15,0,11},{15,5,7},{15,10,3},{16,3,8},{16,8,4},{16,13,0},{17,1,9},{17,6,5},{17,11,1},{18,4,6},{18,9,2},{19,2,7},{19,7,3},{20,0,8},{20,5,4},{20,10,0},{21,3,5},{21,8,1},{22,1,6},{22,6,2},{23,4,3},{24,2,4},{24,7,0},{25,0,5},{25,5,1},{26,3,2},{27,1,3},{28,4,0},{29,2,1},{30,0,2},{32,1,0}

Robert Zwart - 2 years, 10 months ago

include <iostream>

using namespace std;

int main() { int n=0; for ( int i=0;i<34;i++) for(int j = 0;j < 25 ;j++) for(int k=0; k < 20 ;k++) if (3 i + 4 j + 5*k == 100) n++; cout<<n;

return 0;

}

//Output

//92

Bhaskar Pandey - 1 year, 6 months ago
Vishnu Bhagyanath
Jun 22, 2015

Since 3 x 3x is the variable with the greatest coefficient, let us fix its value and find out the possibilities of the remaining 2. x x can take a value from ( 0 , 1 , 2...8 ) (0,1,2...8) which yields 3 x 3x as ( 0 , 3 , 6...24 ) (0,3,6...24) .

For each value of 3 x 3x , there exists 24 3 x + 1 24-3x +1 solutions to the ordered pair ( y , z ) (y,z) . How? Simple.

Since y y and z z both have coefficient one, the possibility of the ordered pairs would be a symmetric set with values from 0 0 to 24 3 x 24-3x . Which means, there would be 24 3 x + 1 24-3x + 1 ordered pairs in each case.

Now instead of sitting and calculating each value of 24 3 x + 1 24-3x+1 , we could make a peculiar observation regarding the value of the above expression.

Listing out all possibilities of 3 x 3x : 0 , 3 , 6 , 9 , 12 , 15 , 18 , 21 , 24 0,3,6,9,12,15,18,21,24

If you notice, this is a mirrored set of values, i.e. the n t h n^{th} value of the set corresponds to the value of 24 3 n 24- 3n which comes at the place 10 n 10 - n . In simpler terms, ( 24 0 = 24 ) (24-0=24) , ( 24 3 = 21 ) (24-3=21) ... ( 24 24 = 0 ) (24-24 = 0) . Therefore the total would be the sum of all possible values of 3 x + 9 3x+9 (since there is a + 1 +1 in each case ).

0 + 3 + 6 + 9 + 12 + 15 + 18 + 21 + 24 + 9 0 + 3 + 6 + 9 + 12 + 15 + 18 + 21 + 24 + 9 117 \boxed{117}

could you please give a solution for a similar question where all the coefficients i.e x,y,z are not unity?For example 3x+4y+8z=24

AKASH ASHOK - 3 years, 6 months ago

Log in to reply

Since x must be divisible by 4, you can just count the solutions in this case. There are only six solutions:{0,6,0}, {0,4,1}, {0,2,2}, {0,0,3}, {4,3,0},{8,0,0}

Yinchen Wu - 3 years, 5 months ago

Log in to reply

Why not {4,1,1}?

Jeff Wiseman - 3 years, 3 months ago

Log in to reply

@Jeff Wiseman I also know this plz explain

Atique Shahriar - 3 years ago

Using the appropriate generating function 1 / ( (1-x^3) * (1-x^4) * (1-x^8) ) the coëfficiënt of x^24 in the related series expansion is 7, so there are 7 solutions.

Here all the 7 {x,y,z} triples are enumerated: {{0,0,3},{0,2,2},{0,4,1},{0,6,0},{4,1,1},{4,3,0},{8,0,0}}

Robert Zwart - 2 years, 10 months ago

if 3x+4y+5z=100 if x,y,z non negative integer then how many solution of this equation? plz solve this

Atique Shahriar - 3 years ago

Log in to reply

Using the appropriate generating function 1 / ( (1-x^3) * (1-x^4) * (1-x^5) ) the coëfficiënt of x^100 in the related series expansion is 94, so there are 94 solutions.

Here all the 94 {x,y,z} triples are enumerated: {0,0,20},{0,5,16},{0,10,12},{0,15,8},{0,20,4},{0,25,0},{1,3,17},{1,8,13},{1,13,9},{1,18,5},{1,23,1},{2,1,18},{2,6,14},{2,11,10},{2,16,6},{2,21,2},{3,4,15},{3,9,11},{3,14,7},{3,19,3},{4,2,16},{4,7,12},{4,12,8},{4,17,4},{4,22,0},{5,0,17},{5,5,13},{5,10,9},{5,15,5},{5,20,1},{6,3,14},{6,8,10},{6,13,6},{6,18,2},{7,1,15},{7,6,11},{7,11,7},{7,16,3},{8,4,12},{8,9,8},{8,14,4},{8,19,0},{9,2,13},{9,7,9},{9,12,5},{9,17,1},{10,0,14},{10,5,10},{10,10,6},{10,15,2},{11,3,11},{11,8,7},{11,13,3},{12,1,12},{12,6,8},{12,11,4},{12,16,0},{13,4,9},{13,9,5},{13,14,1},{14,2,10},{14,7,6},{14,12,2},{15,0,11},{15,5,7},{15,10,3},{16,3,8},{16,8,4},{16,13,0},{17,1,9},{17,6,5},{17,11,1},{18,4,6},{18,9,2},{19,2,7},{19,7,3},{20,0,8},{20,5,4},{20,10,0},{21,3,5},{21,8,1},{22,1,6},{22,6,2},{23,4,3},{24,2,4},{24,7,0},{25,0,5},{25,5,1},{26,3,2},{27,1,3},{28,4,0},{29,2,1},{30,0,2},{32,1,0}

Robert Zwart - 2 years, 10 months ago
Ashik Shahriar
May 28, 2020

here the possible value of x is 0 to 8. if x=0 then y+z=24 and we have 25C1 or 25 solution. then if x=1 we have 22c1=22 solution. if this process is going on then we can reach to x=8 and y+z=0 and we have only one solution in this case. so the number of possible solution is 25+22+19+16.......+1 = 117

Vinod Kumar
Aug 8, 2018

In the Taylor series expansion of 1/{(1-x^3)(1-x)^2} at x=0, find the coefficient of x^24, using WolframAlpha and get the Answer=117.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...