PUMaC 2014 · 组合（B 组） · 第 5 题

PUMaC 2014 — Combinatorics (Division B) — Problem 5

[ 5 ] Amy has a 2 × 10 puzzle grid which she can use 1 × 1 and 1 × 2 (1 vertical, 2 horizontal) tiles to cover. How many ways can she exactly cover the grid without any tiles overlapping and without rotating the tiles?

解析

[ 5 ] Amy has a 2 × 10 puzzle grid which she can use 1 × 1 and 1 × 2 (1 vertical, 2 horizontal) tiles to cover. How many ways can she exactly cover the grid without any tiles overlapping and without rotating the tiles? Solution: First we note that the two rows of 1 × 10 are independent of each other as there are no tiles that can overlap them both. For a single row, the number of ways to tile a 1 × n row, a is a + a as if the last tile n n − 1 n − 2 is a 1 × 1, there are a ways to tile the rest and if the last tile is 1 × 2, there are a ways n − 1 n − 2 to tile the rest. We see that since a = 1 and a = 2, we have a = 89. 1 2 10 2 Therefore there are 89 = 7921 ways to tile the entire 2 × 10 puzzle grid.