HMMT 二月 2008 · TEAM1 赛 · 第 4 题
HMMT February 2008 — TEAM1 Round — Problem 4
题目详情
- [ 30 ] Let n > 6 be a positive integer. Determine the number of ways to walk from (0 , 0) to ( n, 3) using only up and right unit steps such that the path does not meet the lines y = x or y = x − n + 3 except at the start and at the end. Lattice and Centroids [ 130 ] A d -dimensional lattice point is a point of the form ( x , x , . . . , x ) where x , x , . . . , x are all inte- 1 2 d 1 2 d gers. For a set of d -dimensional points, their centroid is the point found by taking the coordinate- wise average of the given set of points. Let f ( n, d ) denote the minimal number f such that any set of f lattice points in the d -dimensional Euclidean space contains a subset of size n whose centroid is also a lattice point.
解析
- [ 30 ] Let n > 6 be a positive integer. Determine the number of ways to walk from (0 , 0) to ( n, 3) using only up and right unit steps such that the path does not meet the lines y = x or y = x − n + 3 except at the start and at the end. 1 Answer: ( n − 6)( n − 1)( n + 1) Consider the first point of the path that lies on x = 3. 6 There are two possibilities for this point: (3 , 0) and (3 , 1), and there is exactly one valid way of getting to each point from the origin. Similarly, consider the last point of the path that lies on x = n − 3. There are two possibilities: ( n − 3 , 2) and ( n − 3 , 3), and there is exactly one valid way of getting to the destination from each of the two points. Now we count the number of valid paths from each of (3 , 0) and (3 , 1), to each of ( n − 3 , 2) and ( n − 3 , 3), and the answer will be the sum. • From (3 , 1) to ( n − 3 , 2): there are no forbidden points along the way, so there are n − 5 ways. • From (3 , 0) to ( n − 3 , 2): the path must not pass through ( n − 3 , 0), and there is exactly ( ) n − 4 one invalid path. So there are − 1 ways. 2 • From (3 , 1) to ( n − 3 , 3): the path must not pass through (3 , 3), and there is exactly one ( ) n − 4 invalid path. So there are − 1 ways. 2 • From (3 , 0) to ( n − 3 , 3): the path must not pass through ( n − 3 , 0) and (3 , 3), and there ( ) n − 3 are exactly two invalid paths. So there are − 2 ways. 3 Summing, we obtain the answer: ( ) ( ) ( ) 3 2 n − 4 n − 4 n − 3 n − 6 n − n + 6 ( n − 6)( n − 1)( n + 1) n − 5+ − 1+ − 1+ − 2 = = . 2 2 3 6 6 Lattice and Centroids [ 130 ] A d -dimensional lattice point is a point of the form ( x , x , . . . , x ) where x , x , . . . , x are all inte- 1 2 1 2 d d gers. For a set of d -dimensional points, their centroid is the point found by taking the coordinate- wise average of the given set of points. Let f ( n, d ) denote the minimal number f such that any set of f lattice points in the d -dimensional Euclidean space contains a subset of size n whose centroid is also a lattice point.