数列中的存在性问题

一句话

“存在一个……”的问题有两条路：

上面的题目： $1 \sim n$ 能不能排成一行，使任何一个数都不是它左右两侧某两个数的平均数（即没有 $a_{i}, a_{j}, a_{k}$ ， $i < j < k$ ，成等差数列）？

第 1 / 5 步

先随手排
从小到大放： $1, 2$ 之后， $3$ 就被挡住了（ $1, 2, 3$ 成等差）。逐项构造容易走进死路，图上的读数会告诉你“还能不能排完”。
一个关键观察
每一半内部
归纳地造出来
不是 2 的幂也行

先猜后证

$n = 3$ 时， $1, 2, 3$ 的 $6$ 种排列中，有几种符合要求？

种

先选定答案，才能看到结论。

例存在一个无穷数列 $a_{1}, a_{2}, \dots$ ，各项是大于 $1$ 的正整数且两两互质。

“无穷”听起来吓人，可数列允许我们每次只造一项：只要说明前 $n$ 项造好之后，第 $n + 1$ 项总能造出来，由数学归纳法，整个数列就存在。

第 1 / 4 步

例（Erdős–Szekeres 定理的特例）任意 $10$ 个互不相同的实数排成的数列，一定有一个长为 $4$ 的单调（递增或递减）子列。

这里没有人能“造”出那个子列——数列是任给的。我们换个方向：假设没有，然后数一数。

第 1 / 4 步

标签
对第 $i$ 项，令 $x_{i}$ 为以它结尾的最长递增子列的长度， $y_{i}$ 为以它结尾的最长递减子列的长度。

$a_{i} ⟼ (x_{i}, y_{i})$
标签两两不同
假设没有长为 4 的
矛盾

两种思路对照：第 1 站给出了数列，第 2 站只保证子列存在。前者回答“是什么”，后者只回答“有没有”——但当对象是“任给的”时，后者往往是唯一的办法。

练习 1基础

第 1 站的数列中 $a_{1} = 2$ ， $a_{n + 1} = a_{1} a_{2} \dots a_{n} + 1$ 。求 $a_{5}$ 。

练习 2基础

按“奇数在前、偶数在后”的递归构造排 $1 \sim 16$ 。排在第 $2$ 位的数是多少？

练习 3提高

要保证任意 $m$ 个互不相同的实数排成的数列中，一定有长为 $3$ 的单调子列， $m$ 最小是多少？

练习 4挑战

证明：对任意正整数 $n$ ，存在 $n$ 个连续的正整数，它们都是合数。