HMMT 二月 2002 · 冲刺赛 · 第 14 题

HMMT February 2002 — Guts Round — Problem 14

[7] An omino is a 1-by-1 square or a 1-by-2 horizontal rectangle. An omino tiling of a region of the plane is a way of covering it (and only it) by ominoes. How many omino tilings are there of a 2-by-10 horizontal rectangle?

解析

An omino is a 1-by-1 square or a 1-by-2 horizontal rectangle. An omino tiling of a region of the plane is a way of covering it (and only it) by ominoes. How many omino tilings are there of a 2-by-10 horizontal rectangle? Solution: There are exactly as many omino tilings of a 1-by- n rectangle as there are domino tilings of a 2-by- n rectangle. Since the rows don’t interact at all, the number of omino tilings of an m -by- n rectangle is the number of omino tilings of a 1-by- n rectangle m 2 raised to the m th power, F . The answer is 89 = 7921 . n