HMMT 二月 2021 · 团队赛 · 第 10 题
HMMT February 2021 — Team Round — Problem 10
题目详情
- [100] Let n > 1 be a positive integer. Each unit square in an n × n grid of squares is colored either black or white, such that the following conditions hold: • Any two black squares can be connected by a sequence of black squares where every two consec- utive squares in the sequence share an edge; • Any two white squares can be connected by a sequence of white squares where every two consec- utive squares in the sequence share an edge; • Any 2 × 2 subgrid contains at least one square of each color. Determine, with proof, the maximum possible difference between the number of black squares and white squares in this grid (in terms of n ).
解析
- [100] Let n > 1 be a positive integer. Each unit square in an n × n grid of squares is colored either black or white, such that the following conditions hold: • Any two black squares can be connected by a sequence of black squares where every two consec- utive squares in the sequence share an edge; • Any two white squares can be connected by a sequence of white squares where every two consec- utive squares in the sequence share an edge; • Any 2 × 2 subgrid contains at least one square of each color. Determine, with proof, the maximum possible difference between the number of black squares and white squares in this grid (in terms of n ). Proposed by: Yuan Yao Answer: 2 n + 1 if n is odd, 2 n − 2 if n is even. Solution: The first two conditions also imply that there can be no 2 × 2 checkerboards, so the boundary between black squares and white squares is either a lattice path or cycle (if one color encloses the other). Therefore, the set of squares of each color is the interior of a lattice polygon of genus 0 or 1. (In the latter case, the genus-1 color uses all squares on the outer boundary, and the opposite color must be genus-0.) 2 The third condition requires that the perimeter of each color passes through all ( n − 1) interior lattice points, or else there will be a monochromatic 2 × 2 subgrid. Hence, by Pick’s Theorem, the area of one 2 2 2 2 color is at least ( n − 1) / 2 − 1 = ( n − 2 n − 1) / 2, and the difference is at most n − ( n − 2 n − 1) = 2 n +1. For even n , the number of interior lattice points is odd so there is no cycle that only uses them. (In particular, this means that both colors are genus-0.) It is impossible for the perimeter to only go through one boundary point either, so we need to add at least three more boundary points, which means that we lose 2(3 / 2) = 3 from the bound for odd n . Here is one possible set of constructions. Throughout, we’ll label the squares as ( x, y ) , for 1 ≤ x, y ≤ n : • For n = 2, we color (2 , 2) black and the others white. • For odd values of n, we create a comb shape using black squares. Specifically, the base of the comb will consist of the squares ( i, 2) , for i = 2 , 3 , . . . , n − 1 . The teeth of the comb will be (2 k, j ) , n − 1 for k = 1 , 2 , . . . , , and j = 3 , 4 , . . . , n − 1 . 2 • For even values of n > 2 , we make a modified comb shape. The base of the comb will be ( i, 2) n for i = 2 , 3 , . . . , n, and the teeth will be (2 k, j ) for k = 1 , 2 , . . . , − 1 and j = 3 , 4 , . . . , n − 1 . 2 n Furthermore, we add the square ( n, 3) , and the squares ( n − 1 , 2 k + 3) for k = 1 , 2 , . . . , − 2 . 2