作者LiquidTLO (俊偉)
看板Math
標題[其他] 離散一題
時間Wed Sep 9 18:28:35 2020
題目:
https://imgur.com/a/t2rJUCV
題目裡job/candidate都有n個
(a)部分不太懂該如何下手
也不清楚Hint裡引入imaginary entities的作用
(b)部分不清楚推的合不合理
Assume 2 stable matching T1, T2
Assume (j0, c0)∈T1, j0 unmatched in T2
c0 cannot be unmatched in T2 -> rogue couple (j0, c0)
->Assume (j1, c0)∈T2
j1 cannot be unmatched in T1 -> rogue couple (j1, c0)
->Assume (j1, c1)∈T1 -> (j2, c1)∈T2 -> ... ->(jn, cn)∈T1
cn cannot be unmatched in T2, and j0 is the only unmatched in T2
-> (j0, cn)∈T2
-> contradicts to j0 unmatched in T2
-> The statement is true
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.154.94 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1599647320.A.E9C.html
1F：→ hwanger : (a)部份 假設candidate/job為c1,c2,...,cn/j0,..,jn 09/10 00:22
2F：→ hwanger : 就假設c0的喜好排序就是j1,j2,...,jn 並且jk以下就 09/10 00:24
3F：→ hwanger : 不想應徵 而j1的喜好排序是c{j1},c{j2},...,c{jn} 09/10 00:27
4F：→ hwanger : 為免符號混淆 j1的喜好排序改成c{i1},...,c{in} 並 09/10 00:31
5F：→ hwanger : 且c{it}以下就不想應聘 09/10 00:32
6F：→ hwanger : 現在引入imaginary candidate/job Nc1,Nc2,...,Ncn/ 09/10 00:34
7F：→ hwanger : Nj1,Nj2,...,Njn 共2n個節點 對某個c而言 如果js排 09/10 00:37
8F：→ hwanger : 在Njs後面 就代表其實c不想要js這份工作 而對於某個 09/10 00:38
9F：→ hwanger : j而言 如果cs排在Ncs後面就代表j其實不想用cs這個人 09/10 00:40
10F：→ hwanger : 而我們可以改寫c1的喜好排序為 09/10 00:42
11F：→ hwanger : j1,j2,...,j{k-1},Nj1,Nj2,...,Njn,jk,j{k+1},..,jn 09/10 00:43
12F：→ hwanger : 並改寫j1的喜好排序為c{j1},c{j2},...,c{j(t-1)}, 09/10 00:45
13F：→ hwanger : Nc1,Nc2,...,Ncn,c{it},...,c{in} 09/10 00:46
14F：→ hwanger : 其他entities的喜好排序也是依此邏輯修改 09/10 00:49
15F：→ hwanger : 符號還是混亂了 很抱歉 09/10 00:51
16F：→ hwanger : 再去證明按上面所述而排出來的stable matching的確 09/10 00:53
17F：→ hwanger : 滿足原問題的五個條件 細節應該不難補完才對 09/10 00:54
18F：→ hwanger : (b)部份我也是這樣想的 只是中間點點點的部份總感覺 09/10 01:15
19F：→ hwanger : 沒有達到數學上的嚴謹 不過這樣的證明一般還是可以 09/10 01:16
20F：→ hwanger : 被接受的 XD 09/10 01:16
21F：→ hwanger : 補充一下(a)部份 為避免某c比較偏好沒有工作時 所有 09/10 16:31
22F：→ hwanger : 的Nj卻都跑去和Nc媒合 所以每一個Nj的喜好排序為 09/10 16:33
23F：→ hwanger : c1,c2,...,cn,Nc1,Nc2,...,Ncn 相同地 每個Nc都是 09/10 16:34
24F：→ hwanger : j1,j2,...,jn,Nj1,Nj2,...,Njn 09/10 16:35