HMMT 二月 2005 · 冲刺赛 · 第 38 题

HMMT February 2005 — Guts Round — Problem 38

[15] In how many ways can the set of ordered pairs of integers be colored red and blue such that for all a and b , the points ( a, b ), ( − 1 − b, a + 1), and (1 − b, a − 1) are all the same color?

解析

In how many ways can the set of ordered pairs of integers be colored red and blue such that for all a and b , the points ( a, b ), ( − 1 − b, a + 1), and (1 − b, a − 1) are all the same color? Solution: 16 ◦ Let ϕ and ϕ be 90 counterclockwise rotations about ( − 1 , 0) and (1 , 0), respectively. 1 2 Then ϕ ( a, b ) = ( − 1 − b, a + 1), and ϕ ( a, b ) = (1 − b, a − 1). Therefore, the possible 1 2 colorings are precisely those preserved under these rotations. Since ϕ (1 , 0) = ( − 1 , 2), 1 ◦ the colorings must also be preserved under 90 rotations about ( − 1 , 2). Similarly, one can show that they must be preserved under rotations about any point ( x, y ), where x is odd and y is even. Decompose the lattice points as follows: L = { ( x, y ) | x + y ≡ 0 (mod 2) } 1 L = { ( x, y ) | x ≡ y − 1 ≡ 0 (mod 2) } 2 L = { ( x, y ) | x + y − 1 ≡ y − x + 1 ≡ 0 (mod 4) } 3 L = { ( x, y ) | x + y + 1 ≡ y − x − 1 ≡ 0 (mod 4) } 4 Within any of these sublattices, any point can be brought to any other through appro- priate rotations, but no point can be brought to any point in a different sublattice. It follows that every sublattice must be colored in one color, but that different sublattices can be colored differently. Since each of these sublattices can be colored in one of two 4 colors, there are 2 = 16 possible colorings. 1 2 1 2 1 2 1 4 1 3 1 4 1 3 1 2 1 2 1 2 1 3 1 4 1 3 1 4 1 2 1 2 1 2 1 4 1 3 1 4 1 3 1 2 1 2 1 2 1