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

英文解析

38. Massachusetts Avenue is ten blocks long. One boy and one girl live on each block.
    They want to form friendships such that each boy is friends with exactly one girl and viceversa. Nobody wants a friend living more than one block away (but they may be on the same block). How many pairings are possible?
    Solution: 89 Let a be the number of pairings if there are n blocks; we have a =
    n 1
    1 , a = 2, and we claim the Fibonacci recurrence is satisfied. Indeed, if there are n blocks,
    either the boy on block 1 is friends with the girl on block 1, leaving a possible pairings 2
    n − 1
    for the people on the remaining n − 1 blocks, or he is friends with the girl on block 2, inwhich case the girl on block 1 must be friends with the boy on block 2, and then there area possibilities for the friendships among the remaining n − 2 blocks. So a = a + a ,
    n − 2 n n − 1 n − 2
    and we compute: a = 3 , a = 5 , . . . , a = 89 .
    3 4 10