sorting - 随机数字列表中的排序子列表

Question

今天我的一位朋友问我以下问题：

如果我们有一个由n 个不同的实数组成的列表（每个 2 个不相等），随机排序，那么我们至少有多少个是按升序或降序排序的？换句话说，排序后的子列表的最小长度是多少？

例如，如果我们有 3 个随机排序的数字，我们将至少有一个 2 的排序子列表。如果我们有 4 个随机排序的数字，我们仍然至少有一个 2 的排序子列表。但是 n 呢？

非常感谢。

Answer 1

我回答我自己的问题。

如果存在 (r+1)(s+1)+1 个数字的随机不同序列（r,s 是非负整数），则必须存在长度为 r 的升序子序列或长度为降序的子序列s。

这就是 Erdos-Szekeres 定理。