2003-全国卷理-22乙 解-组合数学与计数原理

本题导读

本题核心考查利用组合数学与进制转换原理解决新定义数列项数的逆解问题。解题关键在于理解集合元素 $2^r+2^s+2^t$ 的本质是“二进制下恰有三个数位为 1 的正整数”，将已知项 $b_k=1160$ 转换为二进制形式锁定其指数 $(r,s,t)$，再通过组合数分层计数原理，精确计算出该项在从小到大排列中的序号 $k$。

📌【题干】

Question

（2003年全国卷(理)） 22.【乙】 设 $\{b_n\}$ 是集合 $\{2^r+2^s+2^t\mid 0\le r<s<t\text{ 且 }r,s,t\in \mathbf{Z}\}$ 中所有的数从小到大排列成的数列，已知 $b_k=1160$，求 $k$.

🔍【思路分析】

破题导航

1. 第一步逻辑：解析数值的二进制结构 将十进制数 $1160$ 拆解为 2 的幂次和的形式，等价于将其转换为二进制数，从而确定对应的指数 $r,s,t$ 的值。

2. 第二步逻辑：分层计数构建组合模型 要求该数在数列中的序号 $k$，即求集合中比 $1160$ 小的元素的总个数加 1。根据最高位指数 $t$、次高位指数 $s$、最低位指数 $r$ 的层级大小，利用组合数 ${\text{C}}_n^m$ 进行分类穷举计数：

   • 统计最高位指数小于 $t$ 的元素个数；
   • 统计最高位指数等于 $t$ 且次高位指数小于 $s$ 的元素个数；
   • 统计最高位和次高位指数固定，最低位指数小于 $r$ 的元素个数。

3. 第三步逻辑：求和得出序号 将所有满足条件的组合数求和，加 1 后即得序号 $k$.

✅【答案】

Success

$k=145$

✍【详细解析】

Abstract

第一步：确定 $b_k=1160$ 对应的指数 $(r,s,t)$ 通过不断提取 2 的最大幂次，将 $1160$ 分解为二进制基底：

• 接近 $1160$ 且不大于它的 2 的最大幂次为 $2^{10}=1024$；
• 余数为 $1160-1024=136$；
• 接近 $136$ 且不大于它的 2 的最大幂次为 $2^7=128$；
• 余数为 $136-128=8$；
• 恰好有 $8=2^3$。

因此， $1160$ 可以唯一表示为： $1160=2^{10}+2^7+2^3$ 对照集合元素定义 $2^r+2^s+2^t$ ($0\le r<s<t$)，可得对应的指数分别为： $t=10,s=7,r=3$

第二步：统计集合中所有比 $1160$ 小的数的个数 要使集合中的数 $2^{r^{\prime }}+2^{s^{\prime }}+2^{t^{\prime }}<2^3+2^7+2^{10}$，可按以下三类情况讨论：

• 第一类：最高位指数 $t^{\prime }$ 严格小于 $10$ 此时 $t^{\prime }$ 的可选范围为 $\{2,3,4,5,6,7,8,9\}$（因为要有三个不同的指数， $t^{\prime }$ 至少为 2）。 这意味着只要从 $0$ 到 $9$ 这 $10$ 个候选指数中任选 $3$ 个不同的数作为 $(r^{\prime },s^{\prime },t^{\prime })$，构成的数就一定比 $2^{10}$ 小。 该类情况的元素个数为组合数： $N_1={\text{C}}_{10}^3=\frac{10\times 9\times 8}{3\times 2\times 1}=120$

• 第二类：最高位指数 $t^{\prime }=10$，且次高位指数 $s^{\prime }$ 严格小于 $7$ 此时 $t^{\prime }$ 已经固定。由于 $s^{\prime }<7$， $s^{\prime }$ 和 $r^{\prime }$ 必须从 $0$ 到 $6$ 这 $7$ 个候选指数中任意选取 $2$ 个不同的数。 该类情况的元素个数为组合数： $N_2={\text{C}}_7^2=\frac{7\times 6}{2\times 1}=21$

• 第三类：最高位指数 $t^{\prime }=10$，次高位指数 $s^{\prime }=7$，且最低位指数 $r^{\prime }$ 严格小于 $3$ 此时 $t^{\prime }$ 和 $s^{\prime }$ 均已固定。由于 $r^{\prime }<3$， $r^{\prime }$ 的可选范围仅有 $\{0,1,2\}$ 这 $3$ 个值。 该类情况的元素个数为： $N_3={\text{C}}_3^1=3$

第三步：求总序数 $k$ 比 $1160$ 小的元素总数为： $\sum N=N_1+N_2+N_3=120+21+3=144$

因此， $1160$ 是该数列中从小到大排列的第 $144+1=145$ 个数。 即： $k=145$

最终答案：$145$

💡【考点归纳与避坑指南】

Danger

1. 核心考点：十进制向二进制幂次和的转换，组合数 ${\text{C}}_n^m$ 的分层计数法则（字典序计数原理）。
2. 核心方法：结构映射法。将抽象的数的大小比较，平滑映射为二进制数“按位从高到低”的字典序比较。
3. 避坑指南：

   • 在计算第一类个数 ${\text{C}}_{10}^3$ 时，注意可选的数字库是从 $0$ 到 $9$ 共 10 个数，极易粗心错算为 ${\text{C}}_9^3$。

   • 在计算第三类个数时，注意 $r^{\prime }$ 的可选范围是 $0,1,2$，项数等于 3，必须包含指数为 $0$ 的情况（即 $2^0=1$）。

📖【试题探源与推广】

Tip

1. 试题探源: 本题与【22.甲】互为姊妹题，属组合计数与二进制表示的压轴大题。
2. 结论推广: 将该模型一般化：设数列由所有满足 $0\le p_1<p_2<\cdots <p_m$ 的二进制幂次和 ${\sum }_{i=1}^m{2}^{p_i}$ 从小到大排列而成。若已知某一项的指数序列为 $(p_1,p_2,\dots ,p_m)$，则该项在数列中的序号 $k$ 满足： $k=1+{\sum }_{i=1}^m{\text{C}}_{p_i}^i$ 本题中 $m=3$，指数为 $p_1=3,p_2=7,p_3=10$，直接代入得： $k=1+{\text{C}}_3^1+{\text{C}}_7^2+{\text{C}}_{10}^3=1+3+21+120=145$。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 22.01 计数原理、排列与组合

类题演练 (Links)

• 1981-全国文-03 解-排列与组合的计数
• 2005-全国卷I文-15 填-至少一名女生计数
• 1958-北京-03 解-组合数选法计数