HMMT 二月 2018 · COMB 赛 · 第 10 题
HMMT February 2018 — COMB Round — Problem 10
题目详情
英文原题
- Lily has a 300 × 300 grid of squares. She now removes 100 × 100 squares from each of the four cornersand colors each of the remaining 50000 squares black and white. Given that no 2 × 2 square is coloredin a checkerboard pattern, find the maximum possible number of (unordered) pairs of squares suchthat one is black, one is white and the squares share an edge.
解析
英文解析
- Lily has a 300 × 300 grid of squares. She now removes 100 × 100 squares from each of the four cornersand colors each of the remaining 50000 squares black and white. Given that no 2 × 2 square is coloredin a checkerboard pattern, find the maximum possible number of (unordered) pairs of squares suchthat 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 adjacentpoints 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 thatare 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 vertexin the same column and those on a vertical edge pair with the other vertex in the same row. If wecombine 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 lengthand 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 alternatestbetween all black and all white. Lets say the second row from the top is all white. The 101 rowalternates black and white for the first 100 squares, is all black for the next 100 and alternates betweenwhite and black for the last 100 squares. The next 98 rows alternate between all black and all whitend
(the 102 row is all white). Finally, the bottom 101 rows are a mirror of the top 101 rows with thecolors reversed. We easily verify that this achieves the desired. We illustrate the construction for 300
replaced by 12.