Multinomial?

Find the number of positive integral solutions to x + 2 y + 3 z = 100 x+2y+3z=100 .


The answer is 784.

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.

2 solutions

Consider 3 z + 2 y + x = 100 3z+2y+x = 100 . We note that for a fixed z z and y y , there is only one x x . Therefore we only need to consider n ( z ) n(z) , the number of solutions of y y for a fixed z z . And n ( z ) n(z) is equal to the largest possible y y for the fixed z z . That is n ( z ) = max ( y ( z ) ) = 100 3 z min ( x ) 2 n(z) = \max (y(z)) = \dfrac {100-3z-\min (x)}2 . Since the R H S = 100 RHS=100 is even, this implies that when z z is odd, x x is odd and when z z is even, x x is even.

Therefore, min ( x ) = { 1 when z is odd. 2 when z is even. n ( z ) = { 99 3 z 2 when z is odd. 98 3 z 2 when z is even. \min(x) = \begin{cases} 1 & \text{when }z \text{ is odd.} \\ 2 & \text{ when } z \text{ is even.} \end{cases} \implies n(z) = \begin{cases} \dfrac {99-3z}2 & \text{when }z \text{ is odd.} \\ \dfrac {98-3z}2 & \text{ when } z \text{ is even.} \end{cases}

Since z [ 1 , 32 ] z \in [1,32] the number of positive integer solutions to the equation is:

z = 1 32 n ( z ) = k = 1 16 ( 99 3 ( 2 k 1 ) 2 + 98 3 ( 2 k ) 2 ) = k = 1 16 ( 100 6 k ) = 1600 6 ( 16 ) ( 17 ) 2 = 784 \begin{aligned} \sum_{z=1}^{32} n(z) & = \sum_{k=1}^{16} \left(\frac {99 - 3(2k-1)}2 + \frac {98-3(2k)}2\right) \\ & = \sum_{k=1}^{16} (100 - 6k) = 1600 - \frac {6(16)(17)}2 = \boxed{784} \end{aligned}

Bonus question: prove that the number of solutions in positive integers to the equation x + 2 y + 3 z = N x+2y+3z=N is given by

1 12 ( N 2 6 N + C N ) \frac{1}{12} \left(N^2-6N+C_N \right)

where

C N = { 12 when N 0 ( m o d 6 ) 5 when N 1 ( m o d 6 ) 8 when N 2 ( m o d 6 ) 9 when N 3 ( m o d 6 ) 8 when N 4 ( m o d 6 ) 5 when N 5 ( m o d 6 ) C_N= \begin{cases} 12 &\quad \text{when } N \equiv 0 \pmod6 \\ 5 &\quad \text{when } N \equiv 1 \pmod6 \\ 8 &\quad \text{when } N \equiv 2 \pmod6 \\ 9 &\quad \text{when } N \equiv 3 \pmod6 \\ 8 &\quad \text{when } N \equiv 4 \pmod6 \\ 5 &\quad \text{when } N \equiv 5 \pmod6 \end{cases}

Chris Lewis - 1 year, 4 months ago

Log in to reply

I will do it.....

Nikola Alfredi - 1 year, 4 months ago

I feel bad :(

I did the question but in the excitement I did calculation wrong. I multiplied 17 × \times 8 = 132

It is 136 :( :( :(

Nikola Alfredi - 1 year, 4 months ago

But this question is very good and alot intuitive. I like it

Nikola Alfredi - 1 year, 4 months ago
Richard Desper
Feb 3, 2020

The code below returns the value of 784

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#prints the number of solutions
n = 0
for x in range(100):
    for y in range(50):
        for z in range(33):
            if ((x+1) + 2*(y+1) + 3*(z+1) == 100) :
#remove comment from line below to enumerate all solutions
#                print("Solution: {} {} {}".format(x+1,y+1,z+1))
                n += 1
print("{} solutions".format(n)) 

Output: 784 solutions

Range constraints for x,y, and z easily shown to include minimum and maximum values for solutions to this equation.

Richard Desper - 1 year, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...