A spider is making a web between 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 .
HMMT February
Solution
There are 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 choices there are 2 possibilities, and the st choice is then determined.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.