Track / Stage 5 / 316 of 400 #1396 of 2444

Problem 1396

AIME late

Combinatorics Difficulty 5.7 Prove it Harvard-MIT Mathematics Tournament · United States

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 Q P Q Q$ has value $1 \cdot 2 \cdot 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 Q P Q Q$ is antipalindromic.

There are $2^{1002}$ antipalindromic strings of length $2004$ . Find the sum of the reciprocals of their values.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:
$2005^{1002} / 2004$ !
Consider the product
$\left(\frac{1}{1}+\frac{1}{2004}\right)\left(\frac{1}{2}+\frac{1}{2003}\right)\left(\frac{1}{3}+\frac{1}{2002}\right) \cdots\left(\frac{1}{1002}+\frac{1}{1003}\right) .$
This product expands to $2^{1002}$ 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 represented by exactly one of our $2^{1002}$ 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 denominator, for a total of $2005^{1002}$ / $2004!$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.