Re: [資工] 離散 103北大資工 鴿籠

[Honor1984 (奈何上天造化弄人？)]

※ 引述《q1qip123 (wtlee)》之銘言：
: 想請問 在箭頭那一行
: 若是我假設一數列為 2,1,6,7,8,9,10,5,4,3
: 則 I(1)=length('2,6,7,8,9,10')
:      D(1)=length('10,5,4,3')
:      I(2)=length('1,6,7,8,9,10')
:      D(2)=length('10,5,4,3')
: 那我a1跟a2定義出來的數對(I,D)都是（6,4）
: 不就不會產生n^2+1個數對了？
: 謝謝！http://i.imgur.com/R6lj4uh.jpg
: -----
: Sent from JPTT on my OPPO R7sf.

你的理解有誤

D_1 = length('2, 1') = 2

I_2 = length('1,6,7,8,9,10') = 6

D_2 = length('1') = 1

所以只要數列總數 = n^2 + 1，就找得到長度為n + 1的遞增或遞減數列

你沒有看懂證明

尤其是倒數第二、三段

如果a_i < a_j，則I_i的數列可能包含a_j或不包含a_j

如果包含a_j，顯然I_i >= I_j + 1 => I_i > I_j

如果不包含a_j，那表示存在不包含a_j的遞增數列長度 > I_j => I_i > I_j

如果a_i > a_j，則D_i的數列可能包含a_j或不包含a_j

如果包含a_j，顯然D_i >= D_j + 1 => D_i > D_j

如果不包含a_j，那表示存在不包含a_j的遞減數列長度 > D_j => D_i > D_j

由於(I_i, D_i) = (I_j, D_j)必須要求I_i = I_j且D_i = D_j

所以只要I_i = I_j或D_i = D_j其中一個條件不滿足，

就表示(I_i, D_i) = (I_j, D_j)不成立了

因此證明了這個命題。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.56.10.112
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508833748.A.3ED.html
推 q1qip123: 我理解錯的地方是I_i跟D_i都要包含a_i對吧？
→ q1qip123: 那想請問在a_i<a_j時，如果不包含a_j為甚麼一存在遞增數
→ q1qip123: 列長度>I_j?
→ Honor1984: 只有兩種情況 如果不含a_j的數列I_i比含a_j的少 就選擇
→ Honor1984: 含a_j的
推 q1qip123: 我知道是在討論包不包含a_j
→ q1qip123: 不含a_j的情形 直覺上能接受
→ q1qip123: 但是說不含a_j時，則存在I_i>l_j,這個"存在"不太能接受
→ q1qip123: 抱歉 ,這好像很trivial，但是轉不太過來…
→ Honor1984: 如果不包含a_j的所有遞增數列長度 <= I_j，那這些遞增
→ Honor1984: 數列的長度就不會是I_i，而是包含a_j的數列
→ q1qip123: 好 我懂了 感謝！