HMMT 二月 2005 · TEAM1 赛 · 第 6 题

HMMT February 2005 — TEAM1 Round — Problem 6

[40] Show that for b even, there exists some M such that for every m, n > M with mn even, an m × n rectangle is (1 , b )-tileable.

解析

[40] Show that for b even, there exists some M such that for every m, n > M with mn even, an m × n rectangle is (1 , b )-tileable. Solution: By the diagram below, it is possible to tile a (2 b + 2) × (4 b + 1) rectangle. Since we can already tile a (2 b + 2) × 2 b rectangle by above, and 2 b is relatively prime to 4 b + 1, this will allow us to tile any (2 b + 2) × n rectangle for n sufficiently large. Combining this with the previous problem, this will allow us to tile any m × n rectangle for m and n sufficiently large and m even, completing the proof. To tile the (2 b + 2) × (4 b + 1) rectangle, we first tile the following piece: 2 2 2b-1 2b b+1 This is then combined with two 2 × 2 b rectangles, a 2 b × b rectangle, and a 2 b × (2 b + 1) rectangle as follows: 2 x 2b 2b x 2b+1 2b x b 2 x 2b