HMMT 二月 2011 · ALGCOMB 赛 · 第 14 题

英文解析

14. The ordered pairs (2011 , 2) , (2010 , 3) , (2009 , 4) , . . . , (1008 , 1005), (1007 , 1006) are written from left toright on a blackboard. Every minute, Elizabeth selects a pair of adjacent pairs ( x , y ) and ( x , y ), withi i j j
    ( )
    x y x x y yi i j i i j
    ( x , y ) left of ( x , y ), erases them, and writes , in their place. Elizabeth continuesi i j jy xj jthis process until only one ordered pair remains. How many possible ordered pairs ( x, y ) could appearon the blackboard after the process has come to a conclusion?
    Answer: 504510 First, note that none of the numbers will ever be 0. Let ? denote the replacementoperation. For each pair on the board ( x , y ) define its primary form to be ( x , y ) and its secondaryi i i ixform to be [ x y , ]. Note that the primary form determines the secondary form uniquely and viceii iversa. In secondary form,iy
    ( √ ) ( √ ) ( )
    √ √
    a a a
    1 2 1
    2 2
    [ a , b ] ? [ a , b ] = a b , ? a b , = a b , = [ a , b ] .
    1 1 2 2 1 1 2 2 1 2
    1 2
    b b b
    1 2 2
    Thus we may replace all pairs on the board by their secondary form and use the above rule for ?
    instead. From the above rule, we see that if the leftmost number on the board is x , then after oneminute it will be x or x depending on whether it was erased in the intervening step, and similarly for 2
    the rightmost number. Let k be the number of times the leftmost pair is erased and n be the numberof times the rightmost pair is erased. Then the final pair is
    [ ]
    ( )nk 2
    1007
    4022 , . (2)2
    1006
    Any step except the last cannot involve both the leftmost and rightmost pair, so k + n ≤ 1005. Sinceevery pair must be erased at least once, k, n ≥ 1. Every pair of integers satisfying the above can occur,
    for example, by making 1005 − k − n moves involving only the pairs in the middle, then making k − 1
    moves involving the leftmost pair, and finally n moves involving the rightmost pair.
    1004 1005 − k 1004
    ∑ ∑ ∑
    In light of (2), the answer is the number of possible pairs ( k, n ), which is 1 = 1005 − k =
    n =1
    k =1 k =1
    1004
    ∑
    1004 · 1005
    k = = 504510.
    k =12 2