Question

从整数集合 $\{1, 2, 3, \ldots, 2009\}$ 中选出 $k$ 个数对 $\{a_i, b_i\}$ ，满足 $a_i \lt b_i$ ，且任意两个数对没有公共元素。已知所有和 $a_i + b_i$ 互不相同，并且都不超过 $2009$ 。求 $k$ 的最大可能值。

From the set of integers $\{1, 2, 3, \ldots, 2009\},$ choose $k$ pairs $\{a_i, b_i\}$ with $a_i \lt b_i$ so that no two pairs have a common element. Suppose that all the sums $a_i + b_i$ are distinct and less than or equal to $2009.$ Find the maximum possible value of $k.$

答案

答案：803

知识点：双重计数极端原理

难度评级：3060

解答：

令 $S = \sum_{i=1}^{k} (a_i + b_i)$ 。选出的 $2k$ 个元素是互不相同的正整数，所以 $S \ge 1 + 2 + \cdots + 2k$ $= k(2k + 1)$ 。这 $k$ 个和是互不相同且至多为 $2009$ 的整数，因而 $S \le 2009 + 2008 + \cdots$ ${}+ (2010 - k)$ $= \frac{k(4019 - k)}{2}$ 。合并可得 $\begin{aligned} &k(2k + 1) \le \frac{k(4019 - k)}{2} \\ &\implies 4k + 2 \le 4019 - k \\ &\implies k \le \frac{4017}{5} = 803.4, \end{aligned}$ 所以 $k \le 803$ 。

为达到 $k = 803$ ，取数对 $(i,\, 1206 + i)$ ，其中 $1 \le i \le 401$ ，它们的和为偶数 $1208, 1210, \ldots, 2008$ ，再取数对 $(a,\, a + 403)$ ，其中 $402 \le a \le 803$ ，它们的和为奇数 $1207, 1209, \ldots, 2009$ 。用到的元素为 $1$ 到 $803$ ，以及 $805$ 到 $1607$ ，没有重复，并且所有 $803$ 个和互不相同且不超过 $2009$ 。

最大值为 $k = 803$ 。

Let $S = \sum_{i=1}^{k} (a_i + b_i).$ The $2k$ chosen elements are distinct positive integers, so $S \ge 1 + 2 + \cdots + 2k$ $= k(2k + 1).$ The $k$ sums are distinct integers at most $2009,$ so $S \le 2009 + 2008 + \cdots$ ${}+ (2010 - k)$ $= \frac{k(4019 - k)}{2}.$ Combining, $\begin{aligned} &k(2k + 1) \le \frac{k(4019 - k)}{2} \\ &\implies 4k + 2 \le 4019 - k \\ &\implies k \le \frac{4017}{5} = 803.4, \end{aligned}$ so $k \le 803.$

To achieve $k = 803,$ take the pairs $(i,\, 1206 + i)$ for $1 \le i \le 401,$ whose sums are the even numbers $1208, 1210, \ldots, 2008,$ together with the pairs $(a,\, a + 403)$ for $402 \le a \le 803,$ whose sums are the odd numbers $1207, 1209, \ldots, 2009.$ The elements used are $1$ – $803,$ $805$ – $1607$ with no repeats, and all $803$ sums are distinct and at most $2009.$

The maximum is $k = 803.$

2009 AIME II 第 12 题

答案：803

难度评级：3060

解答：

其他年份的第 12 题