2019-北京卷理-20 解-数列新定义

本题导读

本题考查递增子列的概念。核心在于定义分析法、归纳推理法的灵活运用。

📌【题干】

Question

（2019年北京卷理）已知数列 $\{a_n\}$，从中选取第 $i_1,i_2,\dots ,i_m$ 项 ($i_1<i_2<\cdots <i_m$)，若 $a_{i_1}<a_{i_2}<\cdots <a_{i_m}$，则称新数列 $a_{i_1}{a}_{i_2}\dots a_{i_m}$ 为 $\{a_n\}$ 的长度为 $m$ 的递增子列．

(1)写出数列 1, 8, 3, 7, 5, 6, 9 的一个长度为 4 的递增子列；

(2)已知数列 $\{a_n\}$ 的长度为 $p$ 的递增子列的末项的最小值为 $a_{m_0}$，长度为 $q$ 的递增子列的末项的最小值为 $a_{n_0}$．若 $p<q$，求证：$a_{m_0}<a_{n_0}$；

(3)设无穷数列 $\{a_n\}$ 各项均为正整数，且任意两项均不相等．若 $\{a_n\}$ 的长度为 $s$ 的递增子列末项的最小值为 $2s-1$，且长度为 $s$ 末项为 $2s-1$ 的递增子列恰有 $2^{s-1}$ 个 ($s=1,2,\dots$)，求数列 $\{a_n\}$ 的通项公式．

🔍【思路分析】

破题导航

1. 第一问（理解定义）：

   在给定的数字序列中寻找四个数字，要求它们在原序列中的先后顺序不变，且数值依次增大。

2. 第二问（性质证明）：

   • 核心逻辑：任何一个长度为 $q$ 的递增子列，其前 $p$ 项必然构成一个长度为 $p$ 的递增子列。

   • 设长度为 $q$ 的子列末项最小值为 $L_q$，长度为 $p$ 的子列末项最小值为 $L_p$。

   • 考虑任意一个长度为 $q$ 且末项为 $L_q$ 的子列，其第 $p$ 项（记为 $a_k$）满足 $a_k<L_q$（因为是递增子列）。由于 $a_k$ 是某个长度为 $p$ 的子列的末项，故 $L_p\le a_k$，从而推导出 $L_p<L_q$。

3. 第三问（规律构造）：

   • 观察条件：$s=1$ 时，末项最小值 $1$，个数 $1$；$s=2$ 时，末项最小值 $3$，个数 $2$。

   • 尝试构造：为了让末项尽量小且数量成倍增加，考虑成对互换顺序。

   • 猜想：数列为 $2,1,4,3,6,5,\dots ,2n,2n-1,\dots$。

   • 验证：使用数学归纳法证明该数列满足递增子列的数量要求。

✅【答案】

点击查看答案

(1)如 $1,3,5,6$（答案不唯一）。

(2)证明见解析。

(3)$a_n=n+(-1{)}^{n+1}$。

✍【详细解析】

Abstract

(1)解：

满足题意的一个长度为 4 的递增子列为：1, 3, 5, 6（或 1, 3, 5, 9 等，写出一个即可）。

(2)证明：

设长度为 $q$ 的任意一个递增子列为 $a_{j_1},a_{j_2},\dots ,a_{j_q}$．

取其前 $p$ 项 $a_{j_1},a_{j_2},\dots ,a_{j_p}$，由于 $p<q$，这 $p$ 项构成一个长度为 $p$ 的递增子列．

记该长度为 $p$ 的子列末项为 $a_{j_p}$，则由递增定义知 $a_{j_p}<a_{j_p+1}<\cdots <a_{j_q}$，特别地有 $a_{j_p}<a_{j_q}$．

根据已知，长度为 $p$ 的递增子列末项最小值为 $a_{m_0}$，所以 $a_{m_0}\le a_{j_p}$．

结合 $a_{j_p}<a_{j_q}$，得 $a_{m_0}<a_{j_q}$．

上述不等式对所有长度为 $q$ 的递增子列的末项 $a_{j_q}$ 均成立，

所以 $a_{m_0}<\min \{a_{j_q}\}=a_{n_0}$．

即证得：$a_{m_0}<a_{n_0}$．

(3)解：

通过观察 $s=1,2$ 的规律，构造数列如下：

当 $n$ 为奇数时，$a_n=n+1$；当 $n$ 为偶数时，$a_n=n-1$．

即数列为：2, 1, 4, 3, 6, 5, …, 2k, 2k-1, …

通项公式可写为：$a_n=n+(-1{)}^{n+1}$．

证明该数列满足题意：

1. 末项最小值：

   对于该数列，要选出长度为 $s$ 的递增子列，每一对数 $(2k,2k-1)$ 中至多只能取一个（因为 $2k>2k-1$ 且 $2k$ 在 $2k-1$ 之前）。

   若要使末项最小，必须在前 $s$ 对数中各取一个。第 $s$ 对数为 $(2s,2s-1)$，其中较小者为 $2s-1$。故长度为 $s$ 的递增子列末项最小值为 $2s-1$。

2. 子列个数：

   使用数学归纳法。

   • $s=1$ 时，子列为 $\{1\}$，末项 $1$，共 $2^0=1$ 个，成立。

   • 假设 $s=k$ 时，末项为 $2k-1$ 的递增子列有 $2^{k-1}$ 个。

   • 当 $s=k+1$ 时，末项需为 $2k+1$。在此之前的项可以从前 $k$ 对中选。

     对于前 $k$ 对中的每一对 $(2i,2i-1)$，可以选 $2i$ 或 $2i-1$。

     但在选第 $k+1$ 项（即 $2k+1$）之前，第 $k$ 项既可以是第 $k$ 对中的 $2k-1$，也可以是第 $k$ 对中的 $2k$。

     每一位都有 2 种选择，前 $k$ 位共有 $2\times 2\times \cdots \times 2$ ($k$ 个 $2$) 种选法吗？

     注意：第 $k$ 项若选 $2k$，它依然小于 $2k+1$。

     实际上，长度为 $s$ 末项为 $2s-1$ 的子列，其前 $s-1$ 项必须分别来自前 $s-1$ 个数对，每一对都有 $\{2i-1,2i\}$ 两种选法。

     故总数为 $2\times 2\times \cdots \times 2$ ($s-1$ 次方) = $2^{s-1}$ 个。

     证毕。

故通项公式为：$a_n=n+(-1{)}^{n+1}$．

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

Danger

1. 新定义压轴题的特点：北京卷的第 20 题通常不考查死记硬背的公式，而是考查“现场学习”能力。

2. 第二问的跳板作用：第二问证明的性质实际上暗示了递增子列的增长规律，为第三问的构造提供了逻辑支撑。

3. 构造法的灵活性：在第三问中，发现“成对翻转”可以保持末项最小值的同时让路径数翻倍，是解决此类问题的直觉突破口。

📖【试题探源与推广】

Tip

本题背景是计算机科学中经典的 LIS问题 (Longest Increasing Subsequence)：

1. 动态规划：在算法竞赛中，通常使用 $O(n\log n)$ 的算法来寻找最长递增子序列。

2. 狄尔沃斯定理 (Dilworth’s Theorem)：一个序列中最长递增子序列的长度，等于将其划分为最少数量的递减子序列的个数。

   北京卷深度：将计算机算法背景转化为纯数学语言，既考查了严谨性，也考查了数学建模的直觉。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 19.07 一般数列的性质

类题演练 (Links)

• 1993-新高考理-25
• 2002-新课标理-22 解-数列的递推关系
• 2003-广东卷-22