In certain elections, voters are divided into groups; in each group a winner is selected, and to win the election one has to win in most groups.
For example, suppose that Alex and Kim compete to become the student representative at your school. Each class could express a preference, and then the candidate who wins in most classes becomes the student representative.
Gerrymandering is when the groups are drawn to favour one candidate. For example, if polls show Alex does better when students are grouped by school year rather than by class, dividing voters by year instead of by class would give Alex an advantage. If the school president changes the groups this way to favour Alex, that is gerrymandering.
Nine voters choose between candidates A and B. Their votes are as follows:
Who wins the elections? How can B win the election by gerrymandering, if we group the voters by groups of 3?
A has 5 votes out of 9 votes, so A wins by direct counting the favorable votes. If we group voters by row (or by column), A still wins the election by winning in 2 out of the 3 groups.
Candidate B can gerrymander by choosing the groupings as follows:
In this case, B wins in 2 out of the 3 groups and hence wins the election.
Suppose that candidates A and B compete in an election, and there are 81 voters divided into groups of 9. If A has very accurate polls (so that A knows in advance who is going to vote for whom) and A can gerrymander, what is the least number of votes that A needs to have, in order to win the election?
To win in a group, A needs 5 favorable votes out of the 9 votes. And A needs to win at least 5 groups out of 9 groups. So to win with the least amount of favorable votes, A needs to win precisely 5 groups with precisely 5 favorable votes in each of these groups (and without favorable votes in the remaining groups). This gives a total of 25 favorable voters that are necessary and sufficient for A to win the election with gerrymandering,
Suppose that candidates A and B compete in an election, and there are 100 voters divided into groups of 10. If A has very accurate polls (so that A knows in advance who is going to vote for whom) and A can gerrymander, what is the least number of votes that A needs to have, in order to win the election?
We show that 35 favorable votes are sufficient for A to win the election. Remark that, to win in a group, A needs 6 favorable votes while to have a tie in a group, A needs 5 favorable votes.
Suppose that candidate A wins in $w$ groups and gets a tie in $t$ groups. Then candidate B gets a tie in $t$ groups and wins in $10-w-t$ groups. Candidate A then wins if $w>10-w-t$, which means that the requested condition is $$2w+t>10\,.$$
If $t=0$, then we must have $w\geq 6$ and hence A would need 36 votes (to win in 6 groups).
If $t$ is even and strictly positive, then we may decrease $t$ by $1$ while keeping the requested inequality, so we can exclude this case.
If $t=1$, then we must have $w\geq 5$ and hence A would need 35 votes (to win in 5 groups and have a tie in 1 group).
If $t$ is odd and strictly larger than $1$, then we can decrease $t$ by $2$ and increase $w$ by $1$, leading to sparing $4$ votes, so we can exclude this case.
