※ 引述《arcadian3 (falco)》之銘言：
: 給定一個數列 1, 2, 3,....,n^2+1 任意排列
: 則當中必定有 n+1個項會遞增(或遞減)
: 其中遞增或遞減的項不一定要連續
: ex:
: 給定一數列 1, 2, 3, 4, 5
: 則會有 n+1=3 個項遞增或遞減
: 例如 1,3,2,4,5 1,4,5為遞增
: 3,4,2,5,1 4,2,1為遞減
: 5,3,4,1,2 5,4,1為遞減
: 請問版上的高手要如何證明這個定理?
: 謝謝
數列<ai>
如果存在n+1項(以上)的遞增子列, 做完
否則的話
考慮Ai是從以ai為首所找到最長的遞增子列的長度
所以, Ai不超過n, i=1,2,...,n^2+1
由鴿龍原理, 至少有n+1個Ai是相同的
於是 ai是遞減數列 #
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.147.19.22