Brainteaser 1746: Party time
From The Sunday Times, 3rd March 1996 [link]
In the volatile world of Ruritanian politics, each of the three parties can safely expect to lose a fixed proportion of its supporters to each of the other parties from one election to the next. Thus, the Story party would retain a fixed proportion of its supporters, and lose fixed proportions (which may differ) to the Laboured party and to the Mauve Shirts, and so on. Three elections ago, the Story party and the Laboured party each won 40,000 votes and the Mauve Shirts won 20,000. Two elections ago, the Story party and the Mauve Shirts each won 35,000 votes, while the Laboured party won 30,000 votes. In the last election the Story party and the Laboured party each won 35,000 votes and the Mauve Shirts won 30,000. The total electorate in the current election remains at 100,000.
What is the minimum number of votes the Mauve Shirts should expect to win in the current election?
[teaser1746]
Hugo are discussing. 
Frits and 
GeoffR, and 
Tony Brooke-Taylor, and 
Pete Good, and 
S2T2 
Jim Randell 9:15 am on 18 July 2023 Permalink |
See also: Enigma 662.
Given election 1 and election 2 we have 9 variables, of the form XY, that denote the fraction of voters for party X in election 1 that voted for party Y in the election 2.
All votes for each party are redistributed among the three parties, so:
and (working in units of 1000 votes) for election 2:
and for election 3:
and for election 4 we have:
where S, L, M must be whole numbers of votes.
The first 3 blocks give us 9 equations in 9 variables, so it looks like we could solve this system and get the answers for the final block.
However if we try to do this, we find that the 9 equations are not enough to solve the system (i.e. we do not have 9 independent equations, so the system of equations is incomplete). And this makes sense, as the puzzle asks us for the minimum number of votes M can expect to win, so the equations will give a range of values for S, L, M.
But we can solve the system by choosing values for some of the variables until the system becomes complete. It turns out that if we give the values for 2 of the variables the rest can be determined.
By dividing the 20k votes for M in the first election into votes that subsequently go to S, L, M, we can determine values for MS, ML, MM and so the remaining values are determined.
This program looks at different ways to allocate the 20k votes in blocks of 1000 votes, and calculates the results of the 4th election, discarding situations where we do not end up with a whole number of votes.
The program runs in 129ms. (Internal runtime is 60ms).
Run: [ @replit ]
from enigma import ( Rational, Matrix, Accumulator, decompose, as_int, seq2str, printf ) Q = Rational() eqs = [ # SS LS MS SL LL ML SM LM MM (( 1, 0, 0, 1, 0, 0, 1, 0, 0), 1), (( 0, 1, 0, 0, 1, 0, 0, 1, 0), 1), (( 0, 0, 1, 0, 0, 1, 0, 0, 1), 1), ((40, 40, 20, 0, 0, 0, 0, 0, 0), 35), (( 0, 0, 0, 40, 40, 20, 0, 0, 0), 30), (( 0, 0, 0, 0, 0, 0, 40, 40, 20), 35), ((35, 30, 35, 0, 0, 0, 0, 0, 0), 35), (( 0, 0, 0, 35, 30, 35, 0, 0, 0), 35), (( 0, 0, 0, 0, 0, 0, 35, 30, 35), 30), ] # validate a fraction in the interval 0 .. 1 def valid(x): if x < 0 or x > 1: raise ValueError() return x # record minimum value for M is 4th election r = Accumulator(fn=min, collect=1) # choose MS, ML, MM as fractions of N N = 20 for (a, b, c) in decompose(N, 3, increasing=0, sep=0, min_v=0): # add these into the mix eqs_ = [ # SS LS MS SL LL ML SM LM MM (( 0, 0, 1, 0, 0, 0, 0, 0, 0), Q(a, N)), (( 0, 0, 0, 0, 0, 1, 0, 0, 0), Q(b, N)), (( 0, 0, 0, 0, 0, 0, 0, 0, 1), Q(c, N)), ] try: vs = Matrix.linear(eqs + eqs_, field=Q, valid=valid) except ValueError: continue # calculate total votes in the 4th election (SS, LS, MS, SL, LL, ML, SM, LM, MM) = vs S = 35*SS + 35*LS + 30*MS L = 35*SL + 35*LL + 30*ML M = 35*SM + 35*LM + 30*MM # check the values are integers try: (S, L, M) = (as_int(1000 * x) for x in (S, L, M)) except ValueError: continue printf("[S={S} L={L} M={M} {vs}]", vs=seq2str(vs)) r.accumulate_data(M, vs) # output solutions M = r.value for vs in r.data: printf("M={M} {vs}", vs=seq2str(vs))Solution: The Mauve Shirts should expect to win at least 30625 votes.
Here is one set of fractions that give the required values:
Note that no-one who votes for M in one election, votes for M in the next election.
But this is not the only set that gives us the minimum value for M, by increasing the value of
Nat line 29, we can find further viable sets of values, for example:However, the fractions in the bottom row are always the same:
Giving the total votes for M in the 4th election:
LikeLike
Jim Randell 10:22 pm on 19 July 2023 Permalink |
The equations can be simplified to give:
The values of x and y can be restricted by noting that the value of the fraction in each box is between 0 and 1.
And we can calculate the number of votes for M in the 4th election:
And the maximum value for z (= x + y) is 1, which gives a minimum value for M = 30625.
All that remains is to show that the minimum value is achievable, which we can do by considering an example, and checking that all the numbers of votes remain whole numbers.
With x = 2/5 and y = 3/5 (as mentioned above) we have:
With these values it is not possible for another election to follow the same pattern keeping the votes as integers.
But, if we allow fractional votes the situation settles into a steady state with (to 2dp):
LikeLike
Hugo 10:18 am on 18 July 2023 Permalink |
According to my calculations the fewest and most votes that each party can expect are
L 32500 – 34060, M 30625 – 32965, S 33750 – 36090.
I’ve forgotten how I got there!
LikeLike
Jim Randell 10:16 pm on 19 July 2023 Permalink |
I agree with these values.
I found there are 122,304 splits of votes from the 1st election that allow whole votes in the 4th election.
LikeLike