Solution: 2014 Winter Final - 9

Author: Michiel Smid

Question

How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 777$, where $x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$ are integers?

(a)

${781 \choose 4}$

(b)

${781 \choose 3}$

(c)

${780 \choose 4}$

(d)

${780 \choose 3}$

Solution

We can use the stars and bars method to solve this problem.

Imagine the first block composes $ x_1 $ stars, the second block composes $ x_2 $ stars, and so on.

We need to insert 3 bars to separate the 4 blocks.

Because we’re inserting 3 bars, we add 3 extra positions

Now, stars to the left of the first bar represent $ x_1 $, stars between the first and second bars represent $ x_2 $, and so on.

The total number of positions is $ 777 + 3 = 780 $

Now we choose 3 positions out of 780 to place the bars

The number of solutions is $ \binom{780}{3} $