Finding the integer solutions to an equation

Printable View

February 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.
February 12th 2011, 06:43 AM
Plato

This sort of problem is ideal for generating functions.
Look at this expansion.
The coefficient of $x^{200}$ is the answer you want.
February 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?
February 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.
February 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

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

Then the ordinary power series generating function is

$f(x) = (x^2 + x^3 + x^4 + x^5)^{12}$
$= x^{24} (1 + x + x^2 + x^3)^{12}$
$= x^{24} \left( \frac{1 - x^4}{1-x} \right) ^ {12}$
$= x^{24} (1-x^4)^{12} (1-x)^{-12}$
$= 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 $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

$\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...
February 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.