Lily has a grid of squares. She now removes squares from each of the four corners and colors each of the remaining 50000 squares black and white. Given that no square is colored in a checkerboard pattern, find the maximum possible number of (unordered) pairs of squares such that one is black, one is white and the squares share an edge.
Solution
First we show an upper bound. Define a grid point as a vertex of one of the squares in the figure. Construct a graph as follows. Place a vertex at each grid point and draw an edge between two adjacent points if that edge forms a black-white boundary. The condition of there being no checkerboard is equivalent to no vertex having degree more than 2. There are vertices that are allowed to have degree 2 and vertices (on the boundary) that can have degree 1. This gives us an upper bound of 49999 edges. We will show that exactly this many edges is impossible. Assume for the sake of contradiction that we have a configuration achieving exactly this many edges. Consider pairing up the degree 1 vertices so that those on a horizontal edge pair with the other vertex in the same column and those on a vertical edge pair with the other vertex in the same row. If we combine the pairs into one vertex, the resulting graph must have all vertices with degree exactly 2. This means the graph must be a union of disjoint cycles. However all cycles must have even length and there are an odd number of total vertices so this is impossible. Thus we have an upper bound of 49998. We now describe the construction. The top row alternates black and white. The next 99 rows alternate between all black and all white. Let's say the second row from the top is all white. The row alternates black and white for the first 100 squares, is all black for the next 100 and alternates between white and black for the last 100 squares. The next 98 rows alternate between all black and all white (the row is all white). Finally, the bottom 101 rows are a mirror of the top 101 rows with the colors reversed. We easily verify that this achieves the desired.