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

HMMT February 2002 — Guts Round — Problem 38

[6] 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 vice- versa. Nobody wants a friend living more than one block away (but they may be on the same block). How many pairings are possible?

解析

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 vice- versa. 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, 2 either the boy on block 1 is friends with the girl on block 1, leaving a possible pairings n − 1 for the people on the remaining n − 1 blocks, or he is friends with the girl on block 2, in which case the girl on block 1 must be friends with the boy on block 2, and then there are a 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