64

The following graphic is a map of the country Mathlandia:


math


You are currently running for reelection, but the polls aren't exactly in your favor. Each square in this grid is a county. Counties with a black dot are voting for you, while counties with a white dot are voting for your opponent. Can Mathlandia be divided (along the gridlines) into five contiguous states of equal area such that a majority of the states have more black dots than white dots?

Community
  • 1
greenturtle3141
  • 9,937
  • 1
  • 35
  • 70

4 Answers4

56

Yes, you can win by dividing the districts like this:

enter image description here

Jay
  • 4,879
  • 3
  • 18
  • 32
50

@Jay already found the solution to this, but I wanted to expand a little more on why it's the only solution:

Since there are 30 counties in total, each state must have 6 counties, giving us a total of 5 states. There must be at least four black dots in a district in order for it to count as a majority, as having 3 would only guarantee a tie. Since we want to win a majority of the states, we need at least 3 states to have a majority of black dots, giving us a minimum of 12 black dots needed to be able to pull off a win. This corresponds to winning three states by the minimum 4 votes (4 black dots), then losing the other two with no votes at all (all white dots).

Interestingly enough, we have exactly 12 black dots on the grid, which means there has to be two states with all white dots. By testing out different possibilities on the grid, we conclude that the only valid all white dot states that can be drawn are precisely the ones in Jay's answer - the other possibilities either break up the grid into pieces less than 6 or make it impossible to put 4 black dots in each of the remaining 3 states. The rest of the grid can then be divided up as in Jay's solution (in fact, the divisions are forced, since we need 4 black dots in each state), giving us our final answer.

HTM
  • 16,305
  • 2
  • 49
  • 114
  • 1
    This could be improved to show what happens if you consider a tie in two of the five areas, a win for blank in one and a 4 pip win for X in two for areas (still "wins" a majority of areas). Then also a tie in four areas and a 4 pip win for X in one area (still considered a win of majority of areas). This just would cover all possible wins as well and why these are eliminated from consideration. – Keeta - reinstate Monica May 03 '19 at 18:57
  • 1
    @Keeta the question specifies "a majority of the states have more black dots than white dots", which your alternatives technically don't fulfill. – Kat May 03 '19 at 21:29
  • 1
    @Keeta Since black only has 12 dots to go around, it isn't possible for black to win with any state having a tie. (2 black, 1 white and 2 tied would take 14 dots; 1 black and 4 tied would take 16 dots.) – Brilliand May 03 '19 at 22:35
  • @eggyal: Because equal-population is commonly a constraint on districting in most countries, to try to ensure equal representation. (It's trivial to gerrymander this (or most any) map if you ignore the equal-population constraint) – smci May 05 '19 at 11:22
  • @smci: I overlooked the constraint in the question that there are exactly five states. – eggyal May 05 '19 at 11:34
  • +1 but there's an additional assumption that isn't spelt out: the counties must also be contiguous. If you remove that constraint there are other solutions. – Denis de Bernardy May 05 '19 at 15:53
  • @DenisdeBernardy Spartacus’s answer contains solutions for which “contiguous” is interpreted differently – HTM May 05 '19 at 18:25
  • 1
    @PiIsNot3: I wouldn't imagine the other three options Spartacus suggests would pass a sniff test in court. – Denis de Bernardy May 05 '19 at 18:27
18

I think @Jay and @PilsNot3 have it right and that their solutions fit what the OP intended best. However, on the off chance that the OP has a different definition of "contiguous", a few extra possibilities open up. Below are some that I could find that rely on "contiguous" allowing

diagonal connections. 4 solutions

Top left is @Jay's solution and probably the intended one. The other solutions are a little more fun, but may be invalid. As @PilsNot3 explained:

each district must have 4 votes for me!

There are likely other solutions utilizing this trick but I didn't want to spend too much time on a solution I myself thought to be invalid.

Spartacus
  • 311
  • 1
  • 4
  • 14
    If it were me and I allowed diagonals, I'd try and restrict it so that two different regions can't diagonal across each other (because in an unrestricted space you can't make that contiguous), i.e. your upper right solution, but not the two lower. – Draco18s no longer trusts SE May 03 '19 at 15:14
  • 3
    @Draco18s Fair point, guess we'll have to start making bridges and tunnels part of the district. – Spartacus May 03 '19 at 17:42
  • 2
    This answer most fits the theme of the question, even though it's not a direct solution. – Bobson May 03 '19 at 23:41
3

Here is another @Spartakus style solution, following @Draco18s's limitation's on crossings:

solution using a single diagonal connection

Syfer Polski
  • 131
  • 1