HMMT 二月 2005 · TEAM2 赛 · 第 6 题
HMMT February 2005 — TEAM2 Round — Problem 6
题目详情
- [40] Let k be an integer such that k | a and k | b . Prove that if an m × n rectangle is ( a, b )-tileable, then 2 k | m or 2 k | n . An Interlude — Discovering One’s Roots [100] k A k th root of unity is any complex number ω such that ω = 1.
解析
- [40] Let k be an integer such that k | a and k | b . Prove that if an m × n rectangle is ( a, b )-tileable, then 2 k | m or 2 k | n . Solution: We prove the following lemma. Lemma. Let k be a positive integer such that k | a and k | b . Then an m × n rectangle is ⌊ ⌋ ⌈ ⌉ ′ ′ a b m ′ m ( a, b ) -tileable if and only if an m × n rectangle is ( , ) -tileable for ≤ m ≤ k k k k ⌊ ⌋ ⌈ ⌉ n n ′ and ≤ n ≤ . (Here, b x c denotes the greatest integer less than or equal to x , k k while d x e denotes the least integer greater than or equal to x .) Proof. Number the rows and columns in order. For each pair 0 ≤ i, j < k , consider the set of squares in a row congruent to i modulo k and in a column congruent to j modulo k . If one square of a type ( a, b ) domino lies in this set, then so does the other. We can therefore partition the rectangle into these sets and then tile these sets instead. ⌊ ⌋ ⌈ ⌉ ′ ′ m ′ m Each such set is a rectangular array of dimensions m × n , with ≤ m ≤ and k k ⌊ ⌋ ⌈ ⌉ n ′ n a b ≤ n ≤ , and a type ( a, b ) domino on the original rectangle is a type ( , ) k k k k ′ ′ domino on this new array. Since all possible pairs ( m , n ) occur, the result follows. ⌊ ⌋ ⌈ ⌉ m m Suppose 2 k - m and 2 k - n . Then at least one of and is odd, so we can choose k k ′ ′ ′ ′ m odd. Likewise we can choose n odd. But then an m × n rectangle has odd area and so cannot be tileable, implying that the m × n rectangle is not tileable. An Interlude — Discovering One’s Roots [100] k A k th root of unity is any complex number ω such that ω = 1. 2