HMMT 二月 2008 · TEAM1 赛 · 第 4 题

英文解析

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 ory = x − n + 3 except at the start and at the end.
   Answer: ( n − 6)( n − 1)( n + 1) Consider the first point of the path that lies on x = 3.1
   There are two possibilities for this point: (3 , 0) and (3 , 1), and there is exactly one valid way 6
   of getting to each point from the origin. Similarly, consider the last point of the path thatlies on x = n − 3. There are two possibilities: ( n − 3 , 2) and ( n − 3 , 3), and there is exactlyone 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), andthe 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.
   • From (3 , 1) to ( n − 3 , 3): the path must not pass through (3 , 3), and there is exactly one 2
   ( )
   n − 4
   invalid path. So there are − 1 ways.
   • From (3 , 0) to ( n − 3 , 3): the path must not pass through ( n − 3 , 0) and (3 , 3), and there 2
   ( )
   n − 3
   are exactly two invalid paths. So there are − 2 ways.
   Summing, we obtain the answer:3
   ( ) ( ) ( )
   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 dgers. 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.