HMMT 十一月 2021 · GEN 赛 · 第 8 题
HMMT November 2021 — GEN Round — Problem 8
题目详情
- Eight points are chosen on the circumference of a circle, labelled P , P , . . . , P in clockwise order. A 1 2 8 route is a sequence of at least two points P , P , . . . , P such that if an ant were to visit these points a a a 1 2 n in their given order, starting at P and ending at P , by following n − 1 straight line segments (each a a 1 n connecting each P and P ), it would never visit a point twice or cross its own path. Find the a a i i +1 number of routes.
解析
- Eight points are chosen on the circumference of a circle, labelled P , P , . . . , P in clockwise order. A 1 2 8 route is a sequence of at least two points P , P , . . . , P such that if an ant were to visit these points a a a 1 2 n in their given order, starting at P and ending at P , by following n − 1 straight line segments (each a a 1 n connecting each P and P ), it would never visit a point twice or cross its own path. Find the a a i i +1 number of routes. Proposed by: Gabriel Wu Answer: 8744 Solution 1: How many routes are there if we are restricted to n available points, and we must use n − 2 all n of them? The answer is n 2 : first choose the starting point, then each move after that must visit one of the two neighbors of your expanding region of visited points (doing anything else would prevent you from visiting every point). Now simply sum over all possible sets of points that you end ( ) ( ) ( ) 8 8 8 6 5 0 up visiting: (8 · 2 ) + (7 · 2 ) + · · · + (2 · 2 ) = 8744. 8 7 2 Solution 2: We use recursion. Let f ( n ) be the answer for n points, with the condition that our path must start at P (so our final answer is 8 f (8)). Then f (1) = 0 and f (2) = 1. n Now suppose n ≥ 3 and suppose the second point we visit is P (1 ≤ i < n ). Then we can either stop i the path there, yielding one possibility. Alternatively, we can continue the path. In this case, note that it may never again cross the chord P P . If the remainder of the path is among the points P , . . . , P , i n 1 i there are f ( i ) possible routes. Otherwise, there are f ( n − i ) possible routes. As a result, n − 1 n − 1 ∑ ∑ f ( n ) = 1 + f ( i ) + f ( n − i ) = ( n − 1) + 2 f ( i ) . i =1 i =1 From here we may compute: n 1 2 3 4 5 6 7 8 f ( n ) 0 1 4 13 40 121 364 1093 Therefore the answer is 8 · 1093 = 8744.