Finding the integer solutions to an equation

Printable View

• Feb 12th 2011, 06:23 AM
janie_t
Finding the integer solutions to an equation
Problem :
A teacher has just completed writing the final examination for his course in mathematics. This examination has 12 questions, whose total value is to be 200 points. In how many ways can the teacher assign the 200 points if each question must count for at least 10, but not more than 25 points and the point value for each question is to be a multiple of 5?

I would like to know what is wrong in the starting point of my solution:
This is equivalent to finding the integer solutions to
5(x1 + x2 + … + x12) = 200 <=> x1 + x2 + … + x12 = 200/5 <=> x1 + x2 + … + x12 = 40
where 10/5 ≤ xi/5 < 25/5 <=> 2 ≤ xi ≤ 5
for all 1 ≤ i ≤ 12.
• Feb 12th 2011, 06:43 AM
Plato
This sort of problem is ideal for generating functions.
Look at this expansion.
The coefficient of $\displaystyle x^{200}$ is the answer you want.
• Feb 12th 2011, 07:12 AM
janie_t
Thanks, this idea of generating function seems to be a good approach, but how am I supposed to find the coefficient of x^200 by hand?
• Feb 12th 2011, 07:17 AM
Plato
Quote:

Originally Posted by janie_t
how am I supposed to find the coefficient of x^200 by hand?

Well that could be the subject of whole course itself.
I think that since the tools are available such as the site I gave you we ought use them.
• Feb 12th 2011, 04:39 PM
awkward
I share Plato's interest in generating functions and computer algebra systems. But if you need to compute the answer by hand, or at least by hand and calculator, here is a way.

Start with the problem in the form: How many integer solutions are there to

$\displaystyle x_1 + x_2 + \dots + x_{12} = 40$ where $\displaystyle 2 \leq x_i \leq 5$.

Then the ordinary power series generating function is

$\displaystyle f(x) = (x^2 + x^3 + x^4 + x^5)^{12}$
$\displaystyle = x^{24} (1 + x + x^2 + x^3)^{12}$
$\displaystyle = x^{24} \left( \frac{1 - x^4}{1-x} \right) ^ {12}$
$\displaystyle = x^{24} (1-x^4)^{12} (1-x)^{-12}$
$\displaystyle = x^{24} \cdot \sum_i \binom{12}{i} (-1)^i x^{4i} \cdot \sum_j \binom{12+j-1}{j} x^j$

We are now in a position to read off the coefficient of $\displaystyle x^{40}$. First a little arithmetic: note that 40 - 24 = 16 and 16 = 0 + 16 = 4 + 12 = 8 + 8 = 12 + 4 = 16 + 0. Then the coefficient we want is

$\displaystyle \binom{12+16-1}{16} - \binom{12}{1} \binom{12+12-1}{12} + \binom{12}{2} \binom{12+8-1}{8} - \binom{12}{3} \binom{12+4-1}{4} + \binom{12}{4}$

Whew...
• Feb 12th 2011, 04:48 PM
Plato
Quote:

Originally Posted by awkward
Whew...

Well as I said, that can be a course in and of itself.