[離散]證明一個數列有趣的性質

[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為遞減

請問版上的高手要如何證明這個定理?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.114.209.29
推 ridodo:直覺是鴿籠原理
→ suker:遞增遞減都好怪 都不考慮中間值1(32)45,245遞增?145為遞增?
→ arcadian3:是利用鴿籠原理沒錯 但是好像要搭配其他的定理
→ Sfly:就是用鴿籠原理, google: Erdos 遞增
→ arcadian3:嗯謝謝