HMMT 二月 2003 · 冲刺赛 · 第 41 题
HMMT February 2003 — Guts Round — Problem 41
题目详情
- [18] A hotel consists of a 2 × 8 square grid of rooms, each occupied by one guest. All the guests are uncomfortable, so each guest would like to move to one of the adjoining rooms (horizontally or vertically). Of course, they should do this simultaneously, in such a way that each room will again have one guest. In how many different ways can they collectively move?
解析
- A hotel consists of a 2 × 8 square grid of rooms, each occupied by one guest. All the guests are uncomfortable, so each guest would like to move to one of the adjoining rooms (horizontally or vertically). Of course, they should do this simultaneously, in such a way that each room will again have one guest. In how many different ways can they collectively move? Solution: 1156 Imagine that the rooms are colored black and white, checkerboard-style. Each guest in a black room moves to an adjacent white room (and vice versa). If, for each such guest, we place a domino over the original room and the new room, we obtain a covering of the 2 × n grid by n dominoes, since each black square is used once and each white square is used once. Applying a similar procedure to each guest who begins in a white room and moves to a black room, we obtain a second domino tiling. Conversely, it is readily verified that any pair of such tilings uniquely determines a movement pattern. Also, it is easy to prove by induction that the number of domino tilings of a 2 × n grid is the ( n + 1)th Fibonacci number (this holds for the base cases n = 1 , 2, and for a 2 × n rectangle, the two rightmost squares either belong to one vertical domino, leaving a 2 × ( n − 1) rectangle to be covered arbitrarily, or to two horizontal dominoes which also occupy the adjoining squares, leaving a 2 × ( n − 2) rectangle to be covered freely; hence, the numbers of tilings satisfy the Fibonacci recurrence). So the number of domino tilings of a 2 × 8 grid is 34, and the number of pairs of such tilings is 2 34 = 1156, the answer.