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, makingstraight lines of silk from one leaf to another, such that no two of the lines of silk cross each other andhe 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, makinga straight line of silk between each consecutive pair of leaves, such that no two of the lines of silk crosseach other and he visits every leaf exactly once. In how many ways can the spider make the base layerof 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 choicesfor where to go next: the nearest untouched leaf in the clockwise direction, and the nearest untouchedleaf in the counterclockwise direction. For, if the spider visited a leaf which is not nearest in somedirection, there are two untouched leaves which are separated by this line of silk, and so the silk wouldeventually cross itself. Thus, for the first n − 2 choices there are 2 possibilities, and the ( n − 1)st choiceis then determined.
Note: This formula can also be derived recursively.