HMMT 二月 2023 · COMB 赛 · 第 2 题

HMMT February 2023 — COMB Round — Problem 2

Compute the number of ways to tile a 3 × 5 rectangle with one 1 × 1 tile, one 1 × 2 tile, one 1 × 3 tile, one 1 × 4 tile, and one 1 × 5 tile. (The tiles can be rotated, and tilings that differ by rotation or reflection are considered distinct.)

解析

Compute the number of ways to tile a 3 × 5 rectangle with one 1 × 1 tile, one 1 × 2 tile, one 1 × 3 tile, one 1 × 4 tile, and one 1 × 5 tile. (The tiles can be rotated, and tilings that differ by rotation or reflection are considered distinct.) Proposed by: Sean Li Answer: 40 Solution: Our strategy is to first place the 1 × 5 and the 1 × 4 tiles since their size restricts their location. We have three cases: • Case 1: first row. There are 4 ways to place the 1 × 4 tile. There is an empty cell next to the 1 × 4 tile, which can either be occupied by the 1 × 1 tile or the 1 × 2 tile (see diagram). In both cases, there are 2 ways to place the remaining two tiles, so this gives 4 · 2 · 2 = 16 ways. • Case 2: middle row. There are 4 ways to place the 1 × 4 tile, and the 1 × 1 tile must go next to it. There are 2 ways to place the remaining two tiles, so this gives 4 · 2 = 8 ways. • Case 3: bottom row. This is the same as Case 1 up to rotation, so there are also 16 ways to place the tiles here. In total, we have 16 + 8 + 16 = 40 ways to place the tiles.