HMMT 二月 2004 · 冲刺赛 · 第 36 题

英文解析

36. For a string of P ’s and Q ’s, the value is defined to be the product of the positions ofthe P ’s. For example, the string P P QP QQ has value 1 · 2 · 4 = 8.
    Also, a string is called antipalindromic if writing it backwards, then turning all the
    P ’s into Q ’s and vice versa, produces the original string. For example, P P QP QQ isantipalindromic.
    1002
    There are 2 antipalindromic strings of length 2004. Find the sum of the reciprocalsof their values.
    1002
    Solution: 2005 / 2004!
    Consider the product
    ( ) ( ) ( ) ( )
    1 1 1 1 1 1 1 1 + + + · · · + .
    1 2004 2 2003 3 2002 1002 1003
    1002
    This product expands to 2 terms, and each term gives the reciprocal of the valueof a corresponding antipalindromic string of P ’s and Q ’s as follows: if we choosethe term 1 /n for the n th factor, then our string has a P in position n and Q inposition 2005 − n ; if we choose the term 1 / (2005 − n ), then we get a Q in positionn and P in position 2005 − n . Conversely, each antipalindromic string has its value
    1002
    represented by exactly one of our 2 terms. So the value of the product is the number we are looking for. But when we simplify this product, the n th factor becomes
    1 /n + 1 / (2005 − n ) = 2005 /n (2005 − n ). Multiplying these together, we get 1002
    factors of 2005 in the numerator and each integer from 1 to 2004 exactly once in the
    1002
    denominator, for a total of 2005 / 2004!.
    ∏
    2004