Question

设集合 $\mathcal{A}$ 含 $90$ 个元素，且是 $\{1, 2, 3, \ldots, 100\}$ 的子集；设 $S$ 为 $\mathcal{A}$ 中元素的和。求 $S$ 可能取值的个数。

Let set $\mathcal{A}$ be a $90$ -element subset of $\{1, 2, 3, \ldots, 100\},$ and let $S$ be the sum of the elements of $\mathcal{A}.$ Find the number of possible values of $S.$

答案

答案：901

知识点：子集极端原理区间内整数计数

难度评级：1890

小提示：

先求最小和最大可能和，再说明两者之间的每个值都能出现

Find the smallest and largest possible sums, then show every value between them occurs

大提示：

如果和还不是最大，则有某个 $k$ 属于 $\mathcal{A}$ ，并满足 $k + 1 \notin \mathcal{A}$ ；将 $k$ 换成 $k + 1$ 会使和恰好增加 $1$

If the sum is not maximal, some element $k$ of $\mathcal{A}$ has $k + 1 \notin \mathcal{A};$ replacing $k$ by $k + 1$ raises the sum by exactly $1$

解答：

最小可能和为 $1 + 2 + \cdots + 90 = 4095$ ，最大可能和为 $11 + 12 + \cdots + 100 = 4995$ 。

中间的每个整数也都能出现。假设 $\mathcal{A}$ 的和为 $S \le 4994$ ，令 $k$ 为 $\mathcal{A}$ 中满足 $k + 1 \notin \mathcal{A}$ 的最小元素。若 $k$ 是 $100$ ，则 $\mathcal{A}$ 必定是以 $100$ 结尾的一段连续整数，即 $\{11, \ldots, 100\}$ ，其和超过 $4994$ 。因此 $k \ne 100$ ，将 $k$ 换成 $k + 1$ 会得到一个含 $90$ 个元素、和为 $S + 1$ 的子集。

所以 $S$ 取遍从 $4095$ 到 $4995$ 的所有值，共有 $4995 - 4095 + 1 = 901$ 个可能值。

The smallest possible sum is $1 + 2 + \cdots + 90 = 4095,$ and the largest is $11 + 12 + \cdots + 100 = 4995.$

Every integer in between also occurs. Suppose $\mathcal{A}$ has sum $S \le 4994,$ and let $k$ be the smallest element of $\mathcal{A}$ with $k + 1 \notin \mathcal{A}.$ If $k$ were $100,$ then $\mathcal{A}$ would be a block of consecutive integers ending at $100,$ namely $\{11, \ldots, 100\},$ whose sum exceeds $4994.$ So $k \ne 100,$ and replacing $k$ by $k + 1$ produces a $90$ -element subset with sum $S + 1.$

Hence $S$ takes every value from $4095$ to $4995,$ for $4995 - 4095 + 1 = 901$ possible values.

2006 AIME I 第 2 题

答案：901

难度评级：1890

小提示：

大提示：

解答：

其他年份的第 2 题