Math Is Fun Forum

cadjeff

Member

Registered: 2007-05-08

Posts: 26

Recurrence relations problem, please help!

Hello all,

i have a problem which is proving difficult (for me anyway!).

This is the question....

suppose a country is divided into N parliamentary constituencies C1,C2,...,Cn

The size of the electorate in C1 is ei (i=1,2,...N)

The constituency Ci is to be represented in parliament by mi members, where mi>1 for all i and
the Sum of mi = M > N. (But i think that's supposed to be M=>N)

Let ri = Mei/E, where the Sum of ei = E

The error in the representation of the constituency Ci is defined as zi = ABS (mi - ri), and the allocation of seats to constituencies is to be done so as to minimise max (z1,z2,...zN)

Let Gn(m) be defined, for n=1,2,...N, as the minimum possible value of max (z1,z2,...,zn) is the resricted problem in which m members are allocated to C1,C2,...,Cn.

A recurrence relation is obtained for Gn(m) and dynamic programming is used to solve the problem.

Ok so that's the problem.

I literally did a couple of weeks on recurrence relations about two years ago and the lecture notes are awful. Not an inspiring lecturer as i remember.

Anyway i don't have a clue what i'm doing, i don't know what sort of form i should be writing it in.....
should it be written in this kind of form for example.....

Xn+1 = KXn+1 + c     X0 = a

X1 = KX0 +c           = Ka + c

X2 = KX1 + c          =K(Ka + c)c     = (K^2)a + Kc + c

etc......

Here's a little made up example that i was hoping would help make the recurrence relation:

There are 8 seats available.

C1 has an electorate of 8500
C2    "                  "      13400
C3   "                     "    4500
C4    "              "          13600

Therefore E = 40,000

And so their Representation ri = Mei/E

C1 has ri = Mei/E = 8*8500/40000 =  1.7
C2 has ri = 2.68
C3 has ri = 0.9
C4 has ri = 2.72

Obviously you must have whole numbers of people representing as you can't have half a person so i chose to round the numbers to their nearest integer so i got:

C1 = 2     C2 = 3    C3 = 1   C4 = 3     but this gives a total of 9 seats and there are only 8 available so i've taken the Ci with the least error and rounded it down, in this case it's C3 with the smallest error of 0.68.

BUT.....how on earth do you start putting something like this into a recurrence relation???

Any help would be much appreciated,

thanks for reading.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Recurrence relations problem, please help!

Hi cadjeff;

Xn+1 = KXn+1 + c     X0 = a

X1 = KX0 +c           = Ka + c

X2 = KX1 + c          =K(Ka + c)c     = (K^2)a + Kc + c

You won't require this. This is a method of solving a recurrence.

As near as I can tell you are trying to fit whole numbers to data such as this

C1 has ri = Mei/E = 8*8500/40000 =  1.7
C2 has ri = 2.68
C3 has ri = 0.9
C4 has ri = 2.72

While minimizing the error created when you round up or down to an integer.

As far as I know this is not solved by a recurrence, but rather by ILP ( Integer Linear Programming). Using ILP I solved your example problem.

It can be set up like this:

Minimize E = abs(c1-1.7) + abs(c2-2.68) + abs(c3-.9) + abs(c4 - 2.72)

Subject to the constraints:

c1 + c2 + c3 + c4 = 8
c1,c2,c3,c4 are integers and >= 0

Since the variables c1,c2,c3,c4 must be integers the computation is done by computer. I ran it off and came up with:

c1=2. c2 =2, c3 = 1, c4=3 with an error of 1.36. This is the smallest error possible while rounding up or down from your Ci's.

Last edited by bobbym (2009-10-16 23:00:36)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.