推 ai305428d:懂了 謝謝^^ 01/27 22:44
→ aoqq12:可以請問一下n^2種可能是怎麼看出來的嗎？ 01/28 00:32
※ 引述《ai305428d (可愛小小羅)》之銘言：
: http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/96/2101.pdf
: 請問第6題
: 選項(a)為什麼是F
: 第7題
: (f) T ...怎麼證?
7.(f)
令Ak為由ak開始之最長遞增字串，Bk為由ak開始之最長遞減字串。
利用矛盾證法，假設沒有長度為n+1之遞增及長度為n+1之遞減
=>1<=Ak<=n , 1<=Bk<=n for all k=1,2,...,(n^2+1)
=>(A1,B1),(A2,B2),...,(A(n^2+1),B(n^2+1))共有n^2可能
=>必存在i!=j，使得(Ai,Bi)=(Aj,Bj) 產生矛盾 故得證
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.126.62