HMMT 十一月 2009 · 冲刺赛 · 第 31 题

HMMT November 2009 — Guts Round — Problem 31

[ 20 ] There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ziplines can go up, stay flat, or go down, but can’t touch each other (this includes touching at their endpoints). Note that you can’t string a zipline between two floors of the same building.

解析

[ 20 ] There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ziplines can go up, stay flat, or go down, but can’t touch each other (this includes touching at their endpoints). Note that you can’t string a zipline between two floors of the same building. Answer: 252 Associate with each configuration of ziplines a path in the plane as follows: Suppose there are k ziplines. Let a , . . . , a be the distances between consecutive ziplines on the left building 0 k ( a is the floor on which the first zipline starts, and a is the distance from the last zipline to the top 0 k of the building). Define b , . . . , b analogously for the right building. The path in the plane consists of 0 k starting at (0 , 0) and going a distance a to the right, b up, a to the right, b up, etc. We thus go 0 0 1 1 from (0 , 0) to (5 , 5) while traveling only up and to the right between integer coordinates. We can check that there is exactly one configuration of ziplines for each such path, so the answer is the number of ( ) 10 paths from (0 , 0) to (5 , 5) where you only travel up and to the right. This is equal to = 252, since 5 there are 10 total steps to make, and we must choose which 5 of them go to the right.