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]
A k th root of unity is any complex number ω such that ω = 1. You may use the followingkfacts: if ω 6 = 1, then
2 k − 1
1 + ω + ω + · · · + ω = 0 ,
k − 1
and if 1 , ω, . . . , ω are distinct, thenk 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 squaresof each color. Then for any M , we can choose m and n larger than M such that n isodd 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 theserectangles is (1 , b )-tileable.
An Interlude — Discovering One’s Roots [100]
A k th root of unity is any complex number ω such that ω = 1. You may use the followingkfacts: if ω 6 = 1, then
2 k − 1
1 + ω + ω + · · · + ω = 0 ,
k − 1
and if 1 , ω, . . . , ω are distinct, thenk 2 k − 1
( x − 1) = ( x − 1)( x − ω )( x − ω ) · · · ( x − ω ) .