HMMT 二月 2005 · TEAM2 赛 · 第 6 题

英文解析

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 .
   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 kwhile 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 , considerthe set of squares in a row congruent to i modulo k and in a column congruent to jmodulo 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 ≤ andk 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 choosek k
   ′ ′ ′ ′
   m odd. Likewise we can choose n odd. But then an m × n rectangle has odd areaand so cannot be tileable, implying that the m × n rectangle is not tileable.
   An Interlude — Discovering One’s Roots [100]
   A k th root of unity is any complex number ω such that ω = 1.k 2