※ 引述《mqazz1 (无法显示)》之铭言： : Show that every real sequence with lm+1 terms contains either an : increasing subsequence with l+1 terms : or a decreasing subsequence with m+1 terms. 题目问 证明每个有nm+1个项目的实数序列中 (为免混淆 我把l改成n) 不是有长度为n+1的递增子序列 就是有长度为m+1的递减子序列 (附带一提 递增递减子"序列"并不需要连续) 首先设序列的每个项目分别为a(1),a(2),......,a(nm+1) 而 x(k) 代表 从a(k)开始的"最长递增子序列"的长度 for all k=1,2,...,nm+1 而 y(k) 代表 从a(k)开始的"最长递减子序列"的长度 for all k=1,2,...,nm+1 用矛盾证法 假设序列a(1),a(2),......,a(nm+1)中 不存在长度为n+1的递增子序列 也不存在长度为m+1的递减子序列 则代表 1≦x(k)≦n 且 1≦y(k)≦m for all k=1,2,...,nm+1 将x和y组合成数对 （x(k),y(k)） 集合{（x(k),y(k)）| k=1,2,...,nm+1} 最多有nm个元素 (因为x(k)和y(k)的范围限制) 而每一个a(k)都会对应到一个数对（x(k),y(k)） k=1,2,...,nm+1 从鸽笼原理得知 必定存在i,j且i≠j 使得（x(i),y(i)）＝（x(j),y(j)） 因为a(i)≠a(j) (题目没有说每个项目皆相异...但好像要相异才能做?) 假如a(i)＜a(j) 则x(i)＞x(j) 矛盾（x(i),y(i)）＝（x(j),y(j)） 假如a(i)＞a(j) 则y(i)＞y(j) 矛盾（x(i),y(i)）＝（x(j),y(j)） 不管哪个都矛盾 所以得知假设错误 因此存在长度为n+1的递增子序列 或存在长度为m+1的递减子序列 -- 有错请指正 谢谢~ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 112.104.202.169 ※ 编辑: volleyer 来自: 112.104.202.169 (10/09 21:40)