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?
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 |
computer solution
