HMMT 二月 2003 · 冲刺赛 · 第 41 题

英文解析

41. A hotel consists of a 2 × 8 square grid of rooms, each occupied by one guest. All theguests are uncomfortable, so each guest would like to move to one of the adjoiningrooms (horizontally or vertically). Of course, they should do this simultaneously, insuch a way that each room will again have one guest. In how many different ways canthey 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 ofthe 2 × n grid by n dominoes, since each black square is used once and each whitesquare is used once. Applying a similar procedure to each guest who begins in a whiteroom and moves to a black room, we obtain a second domino tiling. Conversely, it isreadily 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 × ngrid is the ( n + 1)th Fibonacci number (this holds for the base cases n = 1 , 2, andfor 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 dominoeswhich also occupy the adjoining squares, leaving a 2 × ( n − 2) rectangle to be coveredfreely; hence, the numbers of tilings satisfy the Fibonacci recurrence). So the numberof domino tilings of a 2 × 8 grid is 34, and the number of pairs of such tilings is
    34 = 1156, the answer.2