HMMT 二月 2007 · COMB 赛 · 第 4 题

HMMT February 2007 — COMB Round — Problem 4

[ 4 ] On the Cartesian grid, Johnny wants to travel from (0 , 0) to (5 , 1), and he wants to pass through all twelve points in the set S = { ( i, j ) | 0 ≤ i ≤ 1 , 0 ≤ j ≤ 5 , i, j ∈ Z } . Each step, Johnny may go from one point in S to another point in S by a line segment connecting the two points. How many ways are there for Johnny to start at (0 , 0) and end at (5 , 1) so that he never crosses his own path?

解析

[ 4 ] On the Cartesian grid, Johnny wants to travel from (0 , 0) to (5 , 1), and he wants to pass through all twelve points in the set S = { ( i, j ) | 0 ≤ i ≤ 1 , 0 ≤ j ≤ 5 , i, j ∈ Z } . Each step, Johnny may go from one point in S to another point in S by a line segment connecting the two points. How many ways are there for Johnny to start at (0 , 0) and end at (5 , 1) so that he never crosses his own path? Answer: 252 . Observe that Johnny needs to pass through the points (0 , 0) , (1 , 0) , (2 , 0) , . . . , (5 , 0) in that order, and he needs to pass through (0 , 1) , (1 , 1) , (2 , 1) , . . . , (5 , 1) in that order, or else he will intersect his own path. Then, the problem is equivalent to interlacing those two sequence together, so that the first term is (0 , 0) and the final term is (5 , 1). To do this, we need to select 5 positions out of ( ) 10 10 to have points with x -coordinate 0. Hence the answer is = 252. 5