HMMT 二月 2014 · COMB 赛 · 第 10 题
HMMT February 2014 — COMB Round — Problem 10
题目详情
- An up-right path from ( a, b ) 2 R to ( c, d ) 2 R is a finite sequence ( x , y ) , . . . , ( x , y ) of points 1 1 k k 2 in R such that ( a, b ) = ( x , y ), ( c, d ) = ( x , y ), and for each 1 i < k we have that either 1 1 k k ( x , y ) = ( x + 1 , y ) or ( x , y ) = ( x , y + 1). Two up-right paths are said to intersect if they i +1 i +1 i i i +1 i +1 i i share any point. Find the number of pairs ( A, B ) where A is an up-right path from (0 , 0) to (4 , 4), B is an up-right path from (2 , 0) to (6 , 4), and A and B do not intersect. HMMT 2014 Saturday 22 February 2014 Combinatorics PUT LABEL HERE Name Team ID# Organization Team
Score:
解析
- An up-right path from ( a, b ) ∈ R to ( c, d ) ∈ R is a finite sequence ( x , y ) , . . . , ( x , y ) of points 1 1 k k 2 in R such that ( a, b ) = ( x , y ), ( c, d ) = ( x , y ), and for each 1 ≤ i < k we have that either 1 1 k k ( x , y ) = ( x + 1 , y ) or ( x , y ) = ( x , y + 1). Two up-right paths are said to intersect if they i +1 i +1 i i i +1 i +1 i i share any point. Find the number of pairs ( A, B ) where A is an up-right path from (0 , 0) to (4 , 4), B is an up-right path from (2 , 0) to (6 , 4), and A and B do not intersect. ( ) 8 Answer: 1750 The number of up-right paths from (0 , 0) to (4 , 4) is because any such up- 4 right path is identical to a sequence of 4 U’s and 4 R’s, where U corresponds to a step upwards and R corresponds to a step rightwards. Therefore, the total number of pairs of (possibly intersecting) ( ) 2 8 up-right paths from (0 , 0) to (4 , 4) and (2 , 0) to (6 , 4) is . 4 We will now count the number of intersecting pairs of up-right paths and subtract it to get the answer. Consider an up-right path A from (0 , 0) to (4 , 4) and an up-right path B from (2 , 0) to (6 , 4). If they intersect, take the point ( x, y ) where they first meet each other, and switch the parts of the paths after ′ ′ ( x, y ) to make an up-right path A from (0 , 0) to (6 , 4) and an up-right path B from (2 , 0) to (4 , 4). ′ ′ Conversely, given an up-right path A from (0 , 0) to (6 , 4) and an up-right path B from (2 , 0) to (4 , 4), they must intersect somewhere, so we can again take their first intersection point and switch the ends to get the original up-right path A from (0 , 0) to (4 , 4) and up-right path B from (2 , 0) to (6 , 4), where A and B intersect. Consequently, the number of intersecting pairs of up-right paths is exactly equal to the number of pairs ( )( ) 10 6 of up-right paths from (0 , 0) to (6 , 4) and (2 , 0) to (4 , 4), which is . The number of pairs that 4 4 ( ) ( )( ) 2 8 10 6 do not intersect is therefore − = 4900 − 3150 = 1750. 4 4 4