All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Voting power distribution (Posted on 2005-01-24) Difficulty: 4 of 5
The five owners of Plexus and Co. are voting on a very important decision (Top secret!). Each must vote for or against the decision. They don't necessarily own equal shares of the company, so they don't necessarily have equal voting power. For example, one person might have 5 votes and the other four have 1 vote each. However, it is distributed in a way that a tie is impossible. Obviously, everyone has positive voting power.

There are 2^5=32 different ways that the five people can vote (such as YYNNY, YNNYY, NNNNN, ...). Each way will result in favor or against the decision, depending on how the voting power is distributed.

There are 2^32 different combinations of the 32 outcomes, but not every combination is possible. For example, it is impossible for YYYNN to be in favor of the decision while YYYYN is against the decision, no matter how the voting power is distributed.

Out of the 2^32 different combinations, how many are possible, remembering that combinations where a tie is possible are not allowed?

See The Solution Submitted by Tristan    
Rating: 3.7143 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 4 of 13 |

The possible voting power distributions, including both those that allow a tie and those that do not are listed in the following table:

 1  1  1  1  1      5    3      1
 2  1  1  1  1      6    3                  5
 2  2  1  1  1      7    4     10
 3  1  1  1  1      7    4      5
 2  2  2  1  1      8    4                 10
 3  2  1  1  1      8    4                 20
 4  1  1  1  1      8    4                  5
 3  2  2  1  1      9    5     30
 5  1  1  1  1      9    5      5
 3  2  2  2  1     10    5                 20
 3  3  2  1  1     10    5                 30
 4  2  2  1  1     10    5                 30
 3  3  3  1  1     11    6     10
 4  2  2  2  1     11    6     20
 3  3  2  2  2     12    6                 10
 4  3  2  2  1     12    6                 60
 4  3  3  1  1     12    6                 30
 5  2  2  2  1     12    6                 20
 4  3  3  2  2     14    7                 30
 5  3  3  2  1     14    7                 60
 5  4  3  2  2     16    8                 60
                               81         390

Numbers of ways are tabulated in separate columns for distributions which don't allow for ties and those that do. The voting weights are given in the first five columns and the total of those weights is in column 6.  The next column gives the number of votes needed to win or to tie. The next to last column is populated only for those distributions in which a tie is not possible, and the last is populated for those distributions in which a tie is possible.  In either instance it represents the permutations of the given vote weighting by assigning the weights to different people: for example 2 2 1 1 1 actually represents 10 different arrangements, as there are C(5,2) = 10 ways of choosing which two are the ones to get the extra vote each.

The ways of allocating voting weights that do not allow for ties is shown as the sum of the next to last column: 81.  This is out of a total of 81+390=471 ways in which voting power could be distributed if tying possibilities were also allowed.

The program tries vote weights that add up to 5, 6, etc. and allocates them to A through E in descending (not necessarily strictly) order. It encodes the 32 results of each of the 32 possible ways that 5 people can vote by encoding a 32-digit base-3 number, where each digit represents a 1 for a win and a 2 for a tie vote, so that no subequent distribution is shown that has the same set of 32 results.  The program was allowed to continue past the point where the total of the weights is 64.  In fact, a total of no more than 32 should be necessary, as that represents the limit of each person having twice the voting power as the person before.

DECLARE SUB addPerms (permCt#)
DECLARE FUNCTION fact# (n#)
DECLARE FUNCTION ceil# (x#)
DEFDBL A-Z
DIM SHARED results(99), noResults, pattern(99, 5)
totVotes = 5
CLS
lineupto = 1
DO
 lookedAt = 0
 FOR p1 = ceil(totVotes / 5) TO totVotes - 4
  tv1 = totVotes - p1
  maxp2 = tv1 - 3: IF maxp2 > p1 THEN maxp2 = p1
 FOR p2 = ceil(tv1 / 4) TO maxp2
  tv2 = tv1 - p2
  maxp3 = tv2 - 2: IF maxp3 > p2 THEN maxp3 = p2
 FOR p3 = ceil(tv3 / 3) TO maxp3
  tv3 = tv2 - p3
  maxp4 = tv3 - 1: IF maxp4 > p3 THEN maxp4 = p3
 FOR p4 = ceil(tv3 / 2) TO maxp4
  tv4 = tv3 - p4
 p5 = tv4
 IF p5 <= p4 THEN
  lookedAt = lookedAt + 1
  rslt = 0: pwr3 = 1
  FOR vPat = 1 TO 31
    v5 = vPat MOD 2: v = vPat 2
    v4 = v MOD 2: v = v 2
    v3 = v MOD 2: v = v 2
    v2 = v MOD 2: v = v 2
    v1 = v
    ptrn = v1 * p1 + v2 * p2 + v3 * p3 + v4 * p4 + v5 * p5
    IF ptrn > totVotes / 2 THEN rslt = rslt + pwr3
    IF ptrn = totVots / 2 THEN rslt = rslt + 2 * pwr3
    IF vPat < 31 THEN pwr3 = pwr3 * 3
  NEXT vPat
  newOne = 1
  FOR i = 1 TO noResults
   IF results(i) = rslt THEN
    newOne = 0: EXIT FOR
   END IF
  NEXT i
  IF newOne THEN
   noResults = noResults + 1
   results(noResults) = rslt
   LOCATE lineupto, 1
   pattern(noResults, 1) = p1: PRINT USING "###"; p1;
   pattern(noResults, 2) = p2: PRINT USING "###"; p2;
   pattern(noResults, 3) = p3: PRINT USING "###"; p3;
   pattern(noResults, 4) = p4: PRINT USING "###"; p4;
   pattern(noResults, 5) = p5: PRINT USING "###"; p5;
   PRINT USING "   #### #### "; totVotes; ceil(totVotes / 2);
   addPerms pct
   IF totVotes MOD 2 THEN
     PRINT TAB(32);
     PRINT USING "###"; pct
     totCt = totCt + pct
   ELSE
     PRINT TAB(44); USING "###"; pct
     totCt2 = totCt2 + pct
   END IF
   lineupto = CSRLIN
  END IF
 END IF
 NEXT p4
 NEXT p3
 NEXT p2
 NEXT p1
 tLooked = tLooked + lookedAt
 LOCATE 1, 60: PRINT totVotes; lookedAt; tLooked
 totVotes = totVotes + 1
LOOP UNTIL INKEY$ = CHR$(27)
LOCATE lineupto, 1
PRINT TAB(32); USING "###"; totCt; TAB(44); totCt2

SUB addPerms (permCt)
  DIM nCt(5)
  howManyDiff = 0
  FOR i = 1 TO 5
    IF pattern(noResults, i) <> pattern(noResults, i - 1) THEN
     howManyDiff = howManyDiff + 1
     nCt(howManyDiff) = 1
    ELSE
     nCt(howManyDiff) = nCt(howManyDiff) + 1
    END IF
  NEXT
  t = fact(5)
  FOR i = 1 TO howManyDiff
    t = t / fact(nCt(i))
  NEXT i
  permCt = t
END SUB

FUNCTION ceil (x)
  ceil = -INT(-x)
END FUNCTION

FUNCTION fact (n)
 t = 1
 FOR i = 2 TO n
   t = t * i
 NEXT
 fact = t
END FUNCTION

Edited on January 26, 2005, 1:58 pm
  Posted by Charlie on 2005-01-25 01:44:41

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information