HMMT 二月 2009 · 冲刺赛 · 第 16 题

HMMT February 2009 — Guts Round — Problem 16

[ 9 ] A spider is making a web between n > 1 distinct leaves which are equally spaced around a circle. He chooses a leaf to start at, and to make the base layer he travels to each leaf one at a time, making straight lines of silk from one leaf to another, such that no two of the lines of silk cross each other and he visits every leaf exactly once. In how many ways can the spider make the base layer of the web? Express your answer in terms of n .

解析

[ 9 ] A spider is making a web between n > 1 distinct leaves which are equally spaced around a circle. He chooses a leaf to start at, and to make the base layer he travels to each leaf one at a time, making a straight line of silk between each consecutive pair of leaves, such that no two of the lines of silk cross each other and he visits every leaf exactly once. In how many ways can the spider make the base layer of the web? Express your answer in terms of n . n − 2 Answer: n 2 Solution: There are n ways to choose a starting vertex, and at each vertex he has only two choices for where to go next: the nearest untouched leaf in the clockwise direction, and the nearest untouched leaf in the counterclockwise direction. For, if the spider visited a leaf which is not nearest in some direction, there are two untouched leaves which are separated by this line of silk, and so the silk would eventually cross itself. Thus, for the first n − 2 choices there are 2 possibilities, and the ( n − 1)st choice is then determined. Note: This formula can also be derived recursively.