返回题库

HMMT 二月 2014 · COMB 赛 · 第 10 题

HMMT February 2014 — COMB Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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 kin R such that ( a, b ) = ( x , y ), ( c, d ) = ( x , y ), and for each 1  i < k we have that either 2
    1 1 k k
    ( x , y ) = ( x + 1 , y ) or ( x , y ) = ( x , y + 1). Two up-right paths are said to intersect if theyi +1 i +1 i i i +1 i +1 i ishare 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 pathfrom (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:

解析

英文解析

  1. 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 kin R such that ( a, b ) = ( x , y ), ( c, d ) = ( x , y ), and for each 1 ≤ i < k we have that either 2
    1 1 k k
    ( x , y ) = ( x + 1 , y ) or ( x , y ) = ( x , y + 1). Two up-right paths are said to intersect if theyi +1 i +1 i i i +1 i +1 i ishare 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 pathfrom (2 , 0) to (6 , 4), and A and B do not intersect.
    ( )
    Answer: 1750 The number of up-right paths from (0 , 0) to (4 , 4) is because any such up-8
    right path is identical to a sequence of 4 U’s and 4 R’s, where U corresponds to a step upwards and 4
    R corresponds to a step rightwards. Therefore, the total number of pairs of (possibly intersecting)
    ( )
    up-right paths from (0 , 0) to (4 , 4) and (2 , 0) to (6 , 4) is .82
    We will now count the number of intersecting pairs of up-right paths and subtract it to get the answer.4
    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 theyintersect, 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 endsto 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
    ( ) ( )( )
    8 10 62
    do not intersect is therefore − = 4900 − 3150 = 1750.
    4 4 4