已知数列 $\{a_n\}$，从中选取第 $i_1$ 项，第 $i_2$ 项，$\cdots$，第 $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},\cdots,a_{i_m}$ 为 $\{a_n\}$ 的长度为 $m$ 的递增子列．规定：数列 $\{a_n\}$ 的任意一项都是 $\{a_n\}$ 的长度为 $1$ 的递增子列．
（I）写出数列 $1,8,3,7,5,6,9$ 的一个长度为 $4$ 的递增子列；
（II）已知数列 $\{a_n\}$ 的长度为 $p$ 的递增子列的末项的最小值为 $a_{m_0}$，长度为 $q$ 的递增子列的末项的最小值为 $a_{n_0}$．若 $p<q$，求证：$a_{m_0}<a_{n_0}$；
（III）设无穷数列 $\{a_n\}$ 的各项均为正整数，且任意两项均不相等．若 $\{a_n\}$ 的长度为 $s$ 的递增子列末项的最小值为 $2s-1$，且长度为 $s$ 末项为 $2s-1$ 的递增子列恰有 $2^{s-1}$ 个（$s=1,2,\cdots$），求数列 $\{a_n\}$ 的通项公式．
（I）写出数列 $1,8,3,7,5,6,9$ 的一个长度为 $4$ 的递增子列；
（II）已知数列 $\{a_n\}$ 的长度为 $p$ 的递增子列的末项的最小值为 $a_{m_0}$，长度为 $q$ 的递增子列的末项的最小值为 $a_{n_0}$．若 $p<q$，求证：$a_{m_0}<a_{n_0}$；
（III）设无穷数列 $\{a_n\}$ 的各项均为正整数，且任意两项均不相等．若 $\{a_n\}$ 的长度为 $s$ 的递增子列末项的最小值为 $2s-1$，且长度为 $s$ 末项为 $2s-1$ 的递增子列恰有 $2^{s-1}$ 个（$s=1,2,\cdots$），求数列 $\{a_n\}$ 的通项公式．
【难度】
【出处】
2019年高考北京卷（理）
【标注】
【答案】
略
【解析】
（I）$1,3,5,6$．（答案不唯一）
（II）设长度为 $q$ 末项为 $a_{n_0}$ 的一个递增子列为 $a_{r_1},a_{r_2},\cdots,a_{r_{q-1}},a_{n_0}$．
由 $p<q$，得 $a_{r_q}\leqslant a_{r_{q-1}}<a_{n_0}$．
因为 $\{a_n\}$ 的长度为 $p$ 的递增子列末项的最小值为 $a_{m_0}$．
又 $a_{r_1},a_{r_2},\cdots,a_{r_p}$ 是 $\{a_n\}$ 的长度为 $p$ 的递增子列，
所以 $a_{m_0}\leqslant a_{r_p}$．
所以 $a_{m_0}<a_{n_0}$．
（III）由题设知，所有正奇数都是 $\{a_n\}$ 中的项．
先证明：若 $2m$ 是 $\{a_n\}$ 中的项，则 $2m$ 必排在 $2m-1$ 之前（$m$ 为正整数）．
假设 $2m$ 排在 $2m-1$ 之后．
设 $a_{p_1},a_{p_2},\cdots,a_{p_{m-1}},2m-1$ 是数列 $\{a_n\}$ 的长度为 $m$ 末项为 $2m-1$ 的递增子列，则 $a_{p_1},a_{p_2},\cdots,a_{p_{m-1}},2m-1,2m$ 是数列 $\{a_n\}$ 的长度为 $m+1$ 末项为 $2m$ 的递增子列．与已知矛盾．
再证明：所有正偶数都是 $\{a_n\}$ 中的项．
假设存在正偶数不是 $\{a_n\}$ 中的项，设不在 $\{a_n\}$ 中的最小的正偶数为 $2m$．
因为 $2k$ 排在 $2k-1$ 之前（$k=1,2,\cdots,m-1$），所以 $2k$ 和 $2k-1$ 不可能在 $\{a_n\}$ 的同一个递增子列中．
又 $\{a_n\}$ 中不超过 $2m+1$ 的数为 $1,2,\cdots,2m-2,2m-1,2m+1$，所以 $\{a_n\}$ 的长度为 $m+1$ 且末项为 $2m+1$ 的递增子列个数至多为 $\underbrace{2\times 2\times 2\times\cdots\times 2}_{(m-1)\text{个}}\times 1\times 1=2^{m-1}<2^m$．
与已知矛盾．
最后证明：$2m$ 排在 $2m-3$ 之后（$m\geqslant 2$ 为整数）．
假设存在 $2m(m\geqslant 2)$，使得 $2m$ 排在 $2m-3$ 之前，则 $\{a_n\}$ 的长度为 $m+1$ 且末项为 $2m+1$ 的递增子列的个数小于 $2^m$．与已知矛盾．
综上，数列 $\{a_n\}$ 只可能为 $2,1,4,3,\cdots,2m-3,2m,2m-1,\cdots$．
经验证，数列 $2,1,4,3,\cdots,2m-3,2m,2m-1,\cdots$ 符合条件．
所以 $a_n=\begin{cases}n+1,&&n\text{为奇数}\\n-1,&&n\text{为偶数}\end{cases}$
（II）设长度为 $q$ 末项为 $a_{n_0}$ 的一个递增子列为 $a_{r_1},a_{r_2},\cdots,a_{r_{q-1}},a_{n_0}$．
由 $p<q$，得 $a_{r_q}\leqslant a_{r_{q-1}}<a_{n_0}$．
因为 $\{a_n\}$ 的长度为 $p$ 的递增子列末项的最小值为 $a_{m_0}$．
又 $a_{r_1},a_{r_2},\cdots,a_{r_p}$ 是 $\{a_n\}$ 的长度为 $p$ 的递增子列，
所以 $a_{m_0}\leqslant a_{r_p}$．
所以 $a_{m_0}<a_{n_0}$．
（III）由题设知，所有正奇数都是 $\{a_n\}$ 中的项．
先证明：若 $2m$ 是 $\{a_n\}$ 中的项，则 $2m$ 必排在 $2m-1$ 之前（$m$ 为正整数）．
假设 $2m$ 排在 $2m-1$ 之后．
设 $a_{p_1},a_{p_2},\cdots,a_{p_{m-1}},2m-1$ 是数列 $\{a_n\}$ 的长度为 $m$ 末项为 $2m-1$ 的递增子列，则 $a_{p_1},a_{p_2},\cdots,a_{p_{m-1}},2m-1,2m$ 是数列 $\{a_n\}$ 的长度为 $m+1$ 末项为 $2m$ 的递增子列．与已知矛盾．
再证明：所有正偶数都是 $\{a_n\}$ 中的项．
假设存在正偶数不是 $\{a_n\}$ 中的项，设不在 $\{a_n\}$ 中的最小的正偶数为 $2m$．
因为 $2k$ 排在 $2k-1$ 之前（$k=1,2,\cdots,m-1$），所以 $2k$ 和 $2k-1$ 不可能在 $\{a_n\}$ 的同一个递增子列中．
又 $\{a_n\}$ 中不超过 $2m+1$ 的数为 $1,2,\cdots,2m-2,2m-1,2m+1$，所以 $\{a_n\}$ 的长度为 $m+1$ 且末项为 $2m+1$ 的递增子列个数至多为 $\underbrace{2\times 2\times 2\times\cdots\times 2}_{(m-1)\text{个}}\times 1\times 1=2^{m-1}<2^m$．
与已知矛盾．
最后证明：$2m$ 排在 $2m-3$ 之后（$m\geqslant 2$ 为整数）．
假设存在 $2m(m\geqslant 2)$，使得 $2m$ 排在 $2m-3$ 之前，则 $\{a_n\}$ 的长度为 $m+1$ 且末项为 $2m+1$ 的递增子列的个数小于 $2^m$．与已知矛盾．
综上，数列 $\{a_n\}$ 只可能为 $2,1,4,3,\cdots,2m-3,2m,2m-1,\cdots$．
经验证，数列 $2,1,4,3,\cdots,2m-3,2m,2m-1,\cdots$ 符合条件．
所以 $a_n=\begin{cases}n+1,&&n\text{为奇数}\\n-1,&&n\text{为偶数}\end{cases}$
答案
解析
备注
