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

英文解析

38. In how many ways can the set of ordered pairs of integers be colored red and blue suchthat for all a and b , the points ( a, b ), ( − 1 − b, a + 1), and (1 − b, a − 1) are all the samecolor?
    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, onecan show that they must be preserved under rotations about any point ( x, y ), where xis odd and y is even. Decompose the lattice points as follows:
    L = { ( x, y ) | x + y ≡ 0 (mod 2) }
    L = { ( x, y ) | x ≡ y − 1 ≡ 0 (mod 2) }1
    L = { ( x, y ) | x + y − 1 ≡ y − x + 1 ≡ 0 (mod 4) }2
    L = { ( x, y ) | x + y + 1 ≡ y − x − 1 ≡ 0 (mod 4) }3
    Within any of these sublattices, any point can be brought to any other through appro-4
    priate rotations, but no point can be brought to any point in a different sublattice. Itfollows that every sublattice must be colored in one color, but that different sublatticescan be colored differently. Since each of these sublattices can be colored in one of twocolors, there are 2 = 16 possible colorings.4
    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