Question

定义 $n!!$ 为 $n(n-2)(n-4)\cdots 3 \cdot 1$ （当 $n$ 为奇数时），以及 $n(n-2)(n-4)\cdots 4 \cdot 2$ （当 $n$ 为偶数时）。将 $\sum_{i=1}^{2009} \frac{(2i-1)!!}{(2i)!!}$ 化为最简分数后，它的分母为 $2^a b$ ，其中 $b$ 为奇数。求 $\frac{ab}{10}$ 。

Define $n!!$ to be $n(n-2)(n-4)\cdots 3 \cdot 1$ for $n$ odd and $n(n-2)(n-4)\cdots 4 \cdot 2$ for $n$ even. When $\sum_{i=1}^{2009} \frac{(2i-1)!!}{(2i)!!}$ is expressed as a fraction in lowest terms, its denominator is $2^a b$ with $b$ odd. Find $\frac{ab}{10}.$

答案

答案：401

知识点：阶乘勒让德公式整除性

难度评级：2840

解答：

第 $i$ 项为 $\frac{(2i-1)!!}{(2i)!!}$ ，其分子为奇数，且 $(2i)!! = 2^i \cdot i!$ 。因为 $\binom{2i}{i} = \frac{(2i)!}{i!\,i!} = \frac{2^i (2i-1)!!}{i!}$ 是整数，所以 $i!$ 中的每个奇素数幂也都整除 $(2i-1)!!$ 。因此第 $i$ 项化为最简分数后的分母恰为 $2^{a_i}$ ，其中 $a_i = i + e_i$ ，而 $e_i$ 是 $i!$ 中 $2$ 的指数。数列 $a_i$ 严格递增，所以通分到公分母 $2^{a_{2009}}$ 时，除了最后一项外，每一项都贡献偶数分子，而最后一项贡献奇数分子。因此总和的最简分母恰为 $2^{a_{2009}}$ ，所以 $b = 1$ 。

由勒让德公式， $\begin{aligned} e_{2009} &= 1004 + 502 + 251 \\ &\quad {}+ 125 + 62 + 31 + 15 \\ &\quad {}+ 7 + 3 + 1 \\ &= 2001, \end{aligned}$ 所以 $a = 2009 + 2001 = 4010$ 。因而 $\frac{ab}{10} = \frac{4010 \cdot 1}{10} = 401$ 。

The $i$ th term is $\frac{(2i-1)!!}{(2i)!!}$ with odd numerator, and $(2i)!! = 2^i \cdot i!.$ Because $\binom{2i}{i} = \frac{(2i)!}{i!\,i!} = \frac{2^i (2i-1)!!}{i!}$ is an integer, every odd prime power dividing $i!$ also divides $(2i-1)!!.$ Hence in lowest terms the $i$ th term has denominator exactly $2^{a_i}$ where $a_i = i + e_i$ and $e_i$ is the exponent of $2$ in $i!.$ The $a_i$ strictly increase, so over the common denominator $2^{a_{2009}}$ every term except the last contributes an even numerator while the last contributes an odd one. The sum in lowest terms therefore has denominator exactly $2^{a_{2009}},$ so $b = 1.$

By Legendre's formula, $\begin{aligned} e_{2009} &= 1004 + 502 + 251 \\ &\quad {}+ 125 + 62 + 31 + 15 \\ &\quad {}+ 7 + 3 + 1 \\ &= 2001, \end{aligned}$ so $a = 2009 + 2001 = 4010.$ Then $\frac{ab}{10} = \frac{4010 \cdot 1}{10} = 401.$

2009 AIME II 第 7 题

答案：401

难度评级：2840

解答：

其他年份的第 7 题