HMMT 二月 2018 · COMB 赛 · 第 10 题

10. Lily has a 300 × 300 grid of squares. She now removes 100 × 100 squares from each of the four corners and colors each of the remaining 50000 squares black and white. Given that no 2 × 2 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. Proposed by: Allen Liu Answer: 49998 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 2 × 2 checkerboard 2 2 is equivalent to no vertex having degree more than 2. There are 101 + 4 · 99 = 49405 vertices that are allowed to have degree 2 and 12 · 99 = 1188 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

We now describe the construction. The top row alternates black and white. The next 99 rows alternate st between all black and all white. Lets say the second row from the top is all white. The 101 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 nd (the 102 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. We illustrate the construction for 300 replaced by 12.