Question

令 $m$ 为从前 $14$ 个自然数组成的集合中选出五元素子集的个数，要求这五个数中至少有两个连续。求 $m$ 除以 $1000$ 的余数。

Let $m$ be the number of five-element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find the remainder when $m$ is divided by $1000.$

答案

答案：750

知识点：补集计数双射子集

难度评级：2300

解答：

计算补集：设 $a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5$ 是没有两个连续数的子集。令 $b_i = a_i - (i - 1)$ ，则每个这样的子集对应到 $\{1, \ldots, 10\}$ 中五个不同的数 $b_1 \lt b_2 \lt \cdots \lt b_5$ ，且这个对应可逆，所以没有两个连续数的子集共有 $\binom{10}{5} = 252$ 个。

因此 $m = \binom{14}{5} - \binom{10}{5}$ $= 2002 - 252 = 1750$ ，除以 $1000$ 的余数为 $750$ 。

Count the complement: subsets $a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5$ with no two consecutive. Setting $b_i = a_i - (i - 1)$ turns each such subset into five distinct numbers $b_1 \lt b_2 \lt \cdots \lt b_5$ in $\{1, \ldots, 10\},$ and this map is reversible, so there are $\binom{10}{5} = 252$ subsets with no two consecutive numbers.

Therefore $m = \binom{14}{5} - \binom{10}{5}$ $= 2002 - 252 = 1750,$ and the remainder upon division by $1000$ is $750.$

2009 AIME II 第 6 题

答案：750

难度评级：2300

解答：

其他年份的第 6 题