Problem of the Week

Problem 3 Solution

$\textbf{Congratulations to the following for solving this problem!}$
Ivan – St Bede’s Inter-church School
Alex Davicenko – Hills Road Sixth Form College

There’s a classic way to solve this kind of problems, we call it stars and bars. It is often introduced specifically to prove two theorems of elementary combinatorics concerning the number of solutions to an equation, as shown on Wikipedia [Stars and Bars](https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)).

Back to this question, it asks for non-negative integer solutions to the equation, so we are going to use the second theorem, which is for any pair of positive integers $n$ and $k$ , the number of $k$ -tuples of non-negative integers whose sum is $n$ is equal to the number of multisets of cardinality $n$ taken from a set of size $k$ . In other words, the number of solutions to $x_1 + x_2 + x_3 + \cdots + x_k = n$ (with $x_1, x_2, x_3, \ldots, x_k \geq 0$ ) is

$\binom{n+k-1}{k-1}$

There’s a way to prove it using the stars and bars method on the Wikipedia webpage above. You can check it out if interested.

However, in this question, instead of 1, the coefficient of $x_5$ is 5. So the first thing we need to do is to find out the possible values of $x_5$ . Since $x_5$ is a non-negative integer, and the sum of the 5 unknowns is 15, there are 4 possible values for $x_5$ , namely 0, 1, 2, and 3. Therefore we have divided the equation into 4 cases: