Re: [理工] [離散] 鴿籠 97北大
※ 引述《annheilong (方格子)》之銘言：
: Using the pigeonhole principle, show that
: a list of n^2 + 1 distinct numbers,
: there are either n+1 numbers (not necessarily consecuitve)
: in increasing order
: or
: n+1 numbers in decreasing order.
: (For example, in the list1, 5, 3, 4, 2,
: we have both the increasing list 1, 3, 4
: and the decreasing lists 5, 4, 2 and 5, 3, 2.)
: 想了好久想不出來
: 只有想到要分n個一組，最後會多出一個
: 可是沒辦法找到鴿子數，沒辦法把牠門趕進去籠子Orz
2
假設這n +1個整數序列為a ,a , ... , a
1 2 n^2+1
2
令x 及y 分別表示由a 開始最長的遞增及遞減子序列的長度，k=1,2, ... ,n +1
k k k
利用矛盾證法，假設該整數序列a ,a , ... , a 中不存在長度為n+1的遞增子序列
1 2 n^2+1
且不存在長度為n+1的遞減子序列
2
則1<=x ,y <=n, for all k=1,2, ... ,n +1
k k
2 2
所以集合{ ( x ,y )| k=1,2, ... ,n +1 }的元素個數最多為n
k k
2
由於每個a 唯一對應一組( x ,y ), for all k=1,2, ... ,n +1
k k k
根據鴿籠原理，存在i,j,i<j使得(x ,y )=(x ,y )
i i j j
因為a =\= a
i j
若a < a ，則x > x ，因此(x ,y )=/=(x ,y )，產生矛盾
i j i j i i j j
若a > a ，則y > y ，因此(x ,y )=/=(x ,y )，產生矛盾
i j i j i i j j
所以存在長度為n+1的遞增子序列或長度為n+1的遞減子序列
-----------------------
來源：小黃離散(上)P2-92
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.227.192.228
推
03/12 15:42, , 1F
03/12 15:42, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：