Reverse Partition grouping problem

[ramsey2879]

In an Excel group someone connected with the Texas caucus gave this math problem> how to subdivide the following set of precincts into subsets so that there are a maximum number of subsets from this set with each subset of precincts totaling at least 180 votes. Since the caucus is this month it seems like a quick answer is needed.

----- Original Message -----
From: George Lawshe
To: EXCEL-G@PEACH.EASE.LSOFT.COM
Sent: Wednesday, March 12, 2008 9:18 PM
Subject: Voting List


I am sure all of you have heard about Texas and their "Vote Twice" in the
Presidential Primary in Texas. Well, it is even more complicated than you
realize. Each county has several voting precincts and they caucus in March
to determine who gets additional Delegate votes. This is determined by how
many people voted in our last governor's race in 2006. If a precinct has
less than 180 votes then they must be paired with other precincts. This
means if Pct 2 voted 90 and Pct 3 voted 90, they would be paired.

Well you can imagine the problems if one has 100 plus precincts to try to
match them up so each will be at least 180, but as many groups as possible.

This may be more than Excel can handle, but I thought I would try.

Please see the list below, I have already filtered out those 180 plus. Is
there a way to have Excel search and match the precincts, (numbers in left
column) and show together. Something like:



10,12=180

15,16=189

1,8 =196



Thanks for your help

George




Pct

Votes


1

100


6

51


7

122


8

96


9

133


10

104


11

46


12

76


13

59


14

57


15

67


16

121


17

105


18

119


19

113


20

45


21

52


22

73


23

94


24

77


27

129


28

115


29

30


30

81


31

27


33

101


34

157


35

58


36

21


37

146


38

31


39

25


40

147


41

72


42

0

 

[CRGreathouse]

With a total of 2850 votes, there can't be any more than 16 groups. I think the maximal number of groups is 15, which is easy enough to make:

96 57 27
100 94
101 81
104 77
105 76
113 72
115 67
119 30 31
121 59
122 58
129 52
133 51
146 46
147 45
157 25

with the 21 and 73 anywhere you like.

 

[ramsey2879]

With a total of 2850 votes, there can't be any more than 16 groups. I think the maximal number of groups is 15, which is easy enough to make:

96 57 27
100 94
101 81
104 77
105 76
113 72
115 67
119 30 31
121 59
122 58
129 52
133 51
146 46
147 45
157 25

with the 21 and 73 anywhere you like.

There are not enough votes for 16 * 180 anyway.
I solve it easily also and I wonder if this problem is authentic.