HMMT 二月 2005 · TEAM1 赛 · 第 7 题

HMMT February 2005 — TEAM1 Round — Problem 7

[25] Prove that neither of the previous two problems holds if b is odd. An Interlude — Discovering One’s Roots [100] k A k th root of unity is any complex number ω such that ω = 1. You may use the following facts: if ω 6 = 1, then 2 k − 1 1 + ω + ω + · · · + ω = 0 , k − 1 and if 1 , ω, . . . , ω are distinct, then k 2 k − 1 ( x − 1) = ( x − 1)( x − ω )( x − ω ) · · · ( x − ω ) . 1

解析

[25] Prove that neither of the previous two problems holds if b is odd. Solution: Color the grid black and white in checkerboard fashion. Then if b is odd, the two squares that make up a (1 , b ) domino always have the same color. Therefore, for an m × n rectangle to be (1 , b )-tileable, it must have an even number of squares of each color. Then for any M , we can choose m and n larger than M such that n is odd and 4 - m . A 2 b × n rectangle and an m × n rectangle then contain bn and mn/ 2 squares of each color, respectively. Since both bn and mn/ 2 are odd, neither of these rectangles is (1 , b )-tileable. An Interlude — Discovering One’s Roots [100] k A k th root of unity is any complex number ω such that ω = 1. You may use the following facts: if ω 6 = 1, then 2 k − 1 1 + ω + ω + · · · + ω = 0 , k − 1 and if 1 , ω, . . . , ω are distinct, then k 2 k − 1 ( x − 1) = ( x − 1)( x − ω )( x − ω ) · · · ( x − ω ) .