作者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/cn.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