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

Home > Numbers
Queue weight possibilities 2. (Posted on 2007-05-23) Difficulty: 4 of 5
When a problem is being voted on in the Perplexus queue, the journeymen and scholars post comments and vote on the problem. A "thumbs up" (TU) scores +1 point, a "thumbs down" (TD) scores -1, and a comment with no vote scores 0.

Part one of this problem, which deals with combinations of TU and TD votes can be found here.

Suppose a problem in the queue has A responses and a score of B. Find a formula that gives the number of possible permutations of TU's, TD's and nonvoting comments the problem has received.

Note: For example a problem with 3 responses and a score of +1 has six possibilities:
{+1,0,0}
{0,+1,0}
{0,0,+1}
{+1,+1,-1}
{+1,-1,+1}
{-1,+1,+1}

See The Solution Submitted by Jer    
Rating: 3.0000 (1 votes)

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

I don't think I can avoid Sigma notation:

As mentioned in the solution to the first QW problem, the lowest number of the majority opinion that can be present is |B|; that's when there are zero opposing votes. The remainder of the votes (A - |B|) are neutral.

The maximum number of votes for the majority opinion is [(A + |B|)/2]; that's when there are [(A + |B|)/2] - |B| opposing votes. This may or may not leave one neutral vote.

In any instance, for the given A and B, the numbers of the other votes (opposing and neutral) depend completely on the number of positive votes.

Define i as the number majority-agreeing votes in a particular case, under the conditions of A responses and a score of B. We are here interested in the ways in which the various TU's, TD's and neutrals can be arranged within the list of A members. The TU's are indistinguishable among themselves, as are the TD's and the neutrals.

There are, by definition, i majority votes.  Then there are i - |B| minority votes, and A - (2*i - |B|) neutral votes.  As any value for i is possible between |B| and [(A + |B|)/2], the solution is the sum:

Sigma{i=|B| to [(A + |B|)/2]}   A! / (i! * (i - |B|)! * (A - (2*i - |B|))!)

The A! in the numerator takes into consideration the ways of rearranging all A responses, but since i of them are indistinguishable majority votes, i - |B| are indistinguishable minority votes and A - (2*i - |B|) are indistinguishable neutral comments, the ways of rearranging those within category are divided out, resulting in the summation above for all possible values of i.

Tabulating that for different values of A and B:

    B:    -3       -2        -1          0        1         2         3
A
0                                         1
1                               1         1         1
2                     1         2         3         2         1
3           1         3         6         7         6         3         1
4           4        10        16        19        16        10         4
5          15        30        45        51        45        30        15
6          50        90       126       141       126        90        50
7         161       266       357       393       357       266       161
8         504       784      1016      1107      1016       784       504
9        1554      2304      2907      3139      2907      2304      1554
10       4740      6765      8350      8953      8350      6765      4740
11      14355     19855     24068     25653     24068     19855     14355
12      43252     58278     69576     73789     69576     58278     43252
13     129844    171106    201643    212941    201643    171106    129844
14     388752    502593    585690    616227    585690    502593    388752
15    1161615   1477035   1704510   1787607   1704510   1477035   1161615
16    3465840   4343160   4969152   5196627   4969152   4343160   3465840
17   10329336  12778152  14508939  15134931  14508939  12778152  10329336
18   30759120  37616427  42422022  44152809  42422022  37616427  30759120
19   91538523 110797569 124191258 128996853 124191258 110797569  91538523
20  272290140 326527350 363985680 377379369 363985680 326527350 272290140
from
  4   cls
  5   goto 100
 15   T=0
 20   for P=abs(B) to int((A+abs(B))/2)
 30      T=T+!(A)//(!(P)*!(P-abs(B))*!(A-(2*P-abs(B))))
 40   next
 50   return
100   for A=0 to 20
103       locate 1,A+1
104       print A
105       if A<3 then Lim=A:else Lim=3
110       for B=-Lim to Lim
120          locate 35+10*B,A+1
130          gosub 15
140          print using(10,0),T;
150       next
160   next
 

The score can go above 3 or below -3, so here are some more columns, recognizing that score +n has the same numbers as score -n:

 
   B:      0         1        2         3          4        5          6 
A
0           1
1           1         1
2           3         2         1
3           7         6         3         1
4          19        16        10         4         1
5          51        45        30        15         5         1
6         141       126        90        50        21         6         1
7         393       357       266       161        77        28         7
8        1107      1016       784       504       266       112        36
9        3139      2907      2304      1554       882       414       156
10       8953      8350      6765      4740      2850      1452       615
11      25653     24068     19855     14355      9042      4917      2277
12      73789     69576     58278     43252     28314     16236      8074
13     212941    201643    171106    129844     87802     52624     27742
14     616227    585690    502593    388752    270270    168168     93093
15    1787607   1704510   1477035   1161615    827190    531531    306735
16    5196627   4969152   4343160   3465840   2520336   1665456    996216
17   15134931  14508939  12778152  10329336   7651632   5182008   3198312
18   44152809  42422022  37616427  30759120  23162976  16031952  10171746
19  128996853 124191258 110797569  91538523  69954048  49366674  32099094
20  377379369 363985680 326527350 272290140 210859245 151419816 100640340
from
  4   cls
  5   goto 100
 15   T=0
 20   for P=abs(B) to int((A+abs(B))/2)
 30      T=T+!(A)//(!(P)*!(P-abs(B))*!(A-(2*P-abs(B))))
 40   next
 50   return
100   for A=0 to 20
103       locate 1,A+1
104       print A
105       if A<6 then Lim=A:else Lim=6
110       for B=0 to Lim
120          locate 10*B+5,A+1
130          gosub 15
140          print using(10,0),T;
150       next
160   next

Edited on May 23, 2007, 3:41 pm
  Posted by Charlie on 2007-05-23 15:40:13

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 (10)
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