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

HMMT February 2004 — Guts Round — Problem 36

[12] For a string of P ’s and Q ’s, the value is defined to be the product of the positions of the 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 is antipalindromic. 1002 There are 2 antipalindromic strings of length 2004. Find the sum of the reciprocals of their values. 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, FEBRUARY 28, 2004 — GUTS ROUND ∏ 2004

解析

For a string of P ’s and Q ’s, the value is defined to be the product of the positions of the 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 is antipalindromic. 1002 There are 2 antipalindromic strings of length 2004. Find the sum of the reciprocals of 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 value of a corresponding antipalindromic string of P ’s and Q ’s as follows: if we choose the term 1 /n for the n th factor, then our string has a P in position n and Q in position 2005 − n ; if we choose the term 1 / (2005 − n ), then we get a Q in position n 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