N个人无嫉(且无贪)分汤

度娘你啃我啊。

楼主 asmobia  发布于 2013-01-27 00:03:00 +0800 CST  
今天有 N 个人,一锅汤,还有数量无限制的、无刻度的、形状不规则的容器。

在没有中立仲裁机构也没有其他任何度量工具的情况之下,这 N 个人要如何设计出一套方法,方能无嫉(且无贪)地分完这一锅汤?一滴不剩?

无嫉:分完之后,没有人认为其他任何一个人拿的比自己多。

无贪:对於任何一个人而言,只要他感到无嫉,他就希望结束分汤的动作,他不会因为”还有机会能够多拿汤”,而继续浪费时间下去

注:人与人的判断不同,或许AB两人觉得分得很公平,但由旁观者C看来,A可能多拿了而B可能少拿了。

楼主 asmobia  发布于 2013-01-27 00:04:00 +0800 CST  
先公布 n=3 的答案,甲乙丙代表三个人,ABCDEFG代表杯子。

<1>甲先将汤分为均等的ABC三杯。

<2>如果乙认为ABC三杯当中最多的两杯汤一样多,那麼请丙先选(丙先选所以不会抗议)、乙再选(由於最多的两杯一样多,因此乙一定能够选到最多的,所以不会抗议),最后让甲选(甲自己均分的,所以不会抗议)--比赛结束。

<3>如果乙认为A杯最多、B杯次之,那麼乙将A多出来的部分倒入D杯中,使得A杯剩下的部分A'=B>=C。

<4>
请丙先从A'、B、C三杯中选一杯(丙先选所以不会忌妒)
如果丙没有选A'的话,乙一定要选A'(对於乙而言,A'与B都是最多的,所以乙一定能够选到最多的,因此不会忌妒)
剩下的一杯给甲(除了A'以外,剩下BC两杯都是甲自己均分的,所以甲不会忌妒)

<5>到此为止:
乙丙两人之中有一个人拿到了A',另一个人没有拿到A'
而甲绝对不会拿到A'

<6>请乙丙两人之中,〔没有拿到A'〕的那个人,将D杯均分成为EFG三杯。
然后〔拿到A'〕的那个人先从EFG中选一杯,他先选当然不会忌妒。
然后轮到甲选一杯(为什麼甲不会忌妒〔拿到A'〕的人呢?下面分解。)
最后由分配EFG的人拿剩下的杯子(自己均分的,当然不会忌妒)。

<7>好,全部问题就在当分配EFG三杯的时候,〔拿到A'〕的人可以先选,而甲第二个选,为何甲不会忌妒〔拿到A'〕的人?答案很简单,因为当初是甲将全部的汤分为ABC三杯的,A=B=C。而后来A杯又被乙倒出一点到D杯,因此 A = A'+D = A'+E+F+G。
很明显的,对於甲而言,拿到A'的人,就算同时拿到EFG三杯,总共加起来也不过就是A,而A是当初甲自己均分的,所以甲当然不会忌妒〔拿到A'〕的人先从EFG中选一杯走。


n=3 得证。

楼主 asmobia  发布于 2013-01-27 17:27:00 +0800 CST  


楼主 asmobia  发布于 2013-01-30 19:35:00 +0800 CST  
先说四个人的解答,以免后来到了N人的时候就完全看不懂了。

无嫉:分完之后,不会有任何一个人,想要与另外一个人交换所得到的份额。
无贪:当确定自己不会想要与任何其他人交换所得到的份额时,就想要立刻结束分配;不会为了贪多而继续分下去。

<四人无嫉且无贪,均分汤的方法>
人的命名:玩家1 ,玩家2 ,玩家3 ,玩家4
汤碗的命名:A,B, C, D...

<1>
玩家2 把汤均分为 4 份,摆到 玩家1 ~ 玩家4 的面前。

<2>
玩家2 询问所有人是否有异议,若无,则每人拿自己面前的那一份,工作结束。

<3>
若有异议,则任选一位有异议的人(假设 玩家1 )。请 玩家1 说明他想要跟谁换汤(假设 玩家3 )。
设 玩家1 的汤为 A 汤碗、玩家3 的汤为 B 汤碗。除了 A 汤碗与 B 汤碗以外,其它所有的汤通通倒回大汤锅里面,等待以后再分。
请注意,此时 玩家2 认为 B = A,但 玩家1 认为 B > A 。

<4>
现在请 玩家1 决定一个整数 n >= 10 ,n 需要满足以下条件:如果把 B 汤碗中的汤任意分为 n 份,再请 玩家1 把这 n 份当中他认为最小的 7 份去掉。去掉之后,对於 玩家1 而言,B 剩余的部分仍然大於 A 。
玩家1 要怎麼决定 n 的值呢?很简单。首先,把 B 任意分为 n 份的话,每份的平均值为 B*(1/n) ,而当中最小的 7 份加总起来,必然小於平均值的 7 倍,也就是 B*(7/n)。
换句话说,玩家1 只要取一个较大的 n 值,能够保证 B*(7/n) < (B-A) 就可以了。

<5>
玩家1 决定了 n 值之后,由 玩家2 将 A 与 B 各自均分为 n 份。

<6>
玩家1 从被切成 n 份的 A 中,挑出他认为最小的 3 份,记为 An-2 >= An-1 >= An。

<7>
此外,玩家1 必然可以办到下面两项工作<7-1>与<7-2>的其中一项:
<7-1>
玩家1 从被切成 n 份的 B 中,挑出最大的 3 份,记为 B1 >= B2 >= B3。使得 B1, B2, B3 严格大於 An, An-1, An-2 ,然后再把 B1 和 B2 多出来的部分倒回大汤锅里面去,使得 B1 = B2 = B3 。
或者。。。
<7-2>
玩家1 从被切成 n 份的 B 中,挑出最大的 1 份,再将它均分为 3 份,记为 B1 = B2 = B3 ,并使得 B1, B2, B3 严格大於 An, An-1, An-2 。

<8>
为什麼说 玩家1 一定可以完成<7-1>或<7-2>这两个动作之一呢?这里要使用反证法来证明:

假设 玩家1 无法完成<7-1>,就表示 B3 <= An-2 。同时 An-3 ~ A7 这 (n-9) 个数字每一个都不会比 An-2 更小;而 B3 ~ Bn-7 这 (n-9) 个数字每一个都不会比 B3 更大,因此得出 Bn-7 + Bn-6 + ... + B3 <= An-3 + An-4 + ... + A7
假设 玩家1 无法完成<7-2>,就表示 B1 不大於 A 当中最小 3 份的总和,因此 B1+B2 也不大於 A 当中任意 6 份的总和,故 B2 + B1 <= A6 + A5 + ... + A1
若上述两个假设同时为真,那麼 Bn-7 + Bn-6 + ... + B2 + B1 <= An-3 + An-2 + ... A1 。换句话说,将被分成 n 份的 B 当中,最小的 7 份( Bn-6, Bn-5, ... Bn )去掉之后,玩家1 认为 B 剩下的部分将不大於 A ,--这与第4步的前题相冲突,属於不可能的事件。
因此 玩家1 必然可以完成<7-1>或<7-2>这两个动作之一。

<9>
无论 玩家1 完成了<7-1>还是<7-2>,现在 玩家1 都认为 B1 = B2 = B3 且严格大於 An-2, An-1, An 。


楼主 asmobia  发布于 2013-02-05 07:15:00 +0800 CST  
同时 玩家2 则认为 An-2 = An-1 = An 且都不小於 B1, B2, B3 。

<10>
请 玩家3 来观察这 6 份(B1 ~ B3, An-1 ~ An),并选出自认为最大的 2 份,然后针对最大的那一份进行修剪--把多出来的部分倒回大汤锅里面--直到最大的两份的份量完全相等为止。

<11>
请 玩家4 从这 6 份里面先挑一份。

<12>
然后请 玩家3 从剩下的 5 份里面挑一份,如果刚刚在第10步被修剪的那一份没有被 玩家4 挑走的话,那麼现在 玩家3 必需要选那一份。

<13>
然后请 玩家2 从 An-2,An-1, An 当中选一份。

<14>
最后请 玩家1 从 B1,B2, B3 当中选一份。
剩下没人选的 2 份倒回大汤锅里面,等待下次再分配。

<15>
至此,我们获得 {X1, X2, X3, X4, L0} ,其中 {X1,X2,X3,X4} 为 4 个人个自认为不吃亏的分配方案,而 L0 是大汤锅里面的汤。同时,玩家1 认为自己的 X1 严格大於 玩家2 的 X2 ,其差值记为 x 。

<16>
由 玩家1 决定一个正整数 s ,使得 L0*(4/5)^s < x 。
s 代表了重复下面步骤17到步骤20的次数--每重覆一次,汤锅里面剩余的汤,就缩小成为前一次的 4/5 以下。等到重覆的次数足够多时,汤锅里面剩下的汤 L < x = X1-X2 。此时对於 玩家1 而言,就算 玩家2 将剩下的汤整锅端去,自己也不会嫉妒。
至於 4/5 这个数字的由来,等到各位看到看到第20步的时候自然明白。

<17>
由 玩家1 把 L0 分为 5 等份。

<18>
由 玩家2 从这 5 份中选择最大 3 份,按照 3 份中最小一份进行修剪,制造出他认为并列最大的 3 份。

<19>
由 玩家3 从这 5 份中选择最大 2 份,按照 2 份中最小一份进行修剪,制造出他认为并列最大的 2 份。

<20>
按照 玩家4, 玩家3, 玩家2, 玩家1 的顺序,从现在的 5 份中各自选择自己认为最大或最大之一的一份。如果可能的话,必须优先选择自己修剪过的那一份;这样人人都不会嫉妒彼此的选择。
剩下没人选的那碗汤,就倒回大汤锅里面。

由於在第17步均分的 5 份汤当中,必然有 1 份汤”未曾被修剪过”且”最后被 玩家1 自己拿走”,因此我们可以极端保守地说,从步骤17到步骤20,玩家1 至少成功地分配了 L0*(1/5) 的汤。
剩下的未曾分完的汤(主要是因为在修剪的过程中被倒回大汤桶中),称为 L1 。由於至少有 L0*(1/5) 的汤成功地被分掉,故 L1 <= L0*(4/5)
事实上每次成功分配的汤绝对不只 L0*(1/5) 那麼少,但考虑到那些”修剪”的动作并不是 玩家1 所能控制的,所以我们只计算 玩家1 所能够控制的部分(也就是最后 玩家1 自己拿走的那碗未曾修剪过的汤),故得到 4/5 这个数字。。。这也是第16步里面 (4/5) 这个数字的由来。

<21>
重覆步骤17~20共 s 次。
重覆 s 次之后,我们获得 {X1, X2, X3, X4, Ls} ,其中 {X1,X2,X3,X4} 为 4 个人个自认为不吃亏的分配方案,而 Ls 是汤锅里面剩余的汤,且 Ls < L0*(4/5)^s < x 。
由於 玩家1 在第15步的时候认为 (X1-X2) > x ,故此时 Ls < x < (X1-X2),也就是说就算剩下的汤全部被 玩家2 拿走,玩家1 也不会感到嫉妒--此时我们称 玩家1 对 玩家2 具有〔绝对优势〕。

<22>
玩家2 把剩下的汤分为 12 等份。

<23>
每个玩家都可以投票--如果你认为这 12 份是一样大的就投赞成票,否则就投反对票--很显然 玩家2 自己必投赞成票。

<24>
如果投反对票的每一个人,对於投赞成票的每一个人,都具有〔绝对优势〕的话,则反对无效,直接把这 12 份平分给投赞成票的人,且工作结束。
为甚麼?道理很简单:既然你对我有〔绝对优势〕,那麼就算汤锅里面剩下的东西都归我,你也不会嫉妒我。因此如果反对方的每一人对於赞成方的每一人都有〔绝对优势〕的话,那麼反对方的每一人,当然都不会嫉妒赞成方的众人把剩下的汤均分。

<25>
不然的话,我们必然可以从反对方与赞成方之间各自选出一个人,称为〔反对者〕与〔赞成者〕,且〔反对者〕对〔赞成者〕不具〔绝对优势〕。
然后回归步骤3,让〔反对者〕当 玩家1 ,让〔赞成者〕当 玩家2,这样运行至步骤21的时候,必能建立起〔反对者〕对〔赞成者〕的〔绝对优势〕。

<26>
承上,每次从步骤3运行到步骤21,就会建立起一组〔绝对优势〕的关系。
4 名参赛者最多只有 4^2 = 16 组〔绝对优势〕,因此最多只要重覆 16 次,就人人都有绝对优势了;此时到了第24步的时候,反对一律无效,就可以结束分配工作了。

楼主 asmobia  发布于 2013-02-05 07:15:00 +0800 CST  
看懂楼上的朋友请举手?

楼主 asmobia  发布于 2013-02-05 07:21:00 +0800 CST  
解释思路:

============================
十三楼,〔四人分汤〕的步骤17~步骤20:
<17> 玩家1 将剩下的汤分成 5 份。
<18> 玩家2 选出最大的 3 份,然后将其中较大的那 2 份”修剪”成为与第 3 大的那份相同--修剪出来的汤,倒回桶内等待以后再分。
<19> 玩家3 选出最大的 2 份,然后将其中较大的那 1 份”修剪”成为与第 2 大的那份相同--修剪出来的汤,倒回桶内等待以后再分。
<20> 按照 玩家4、玩家3、玩家2、玩家1 的顺序来选汤;如果可以的话,要优先选择自己修剪过的汤,这样大家都不会忌妒彼此。而剩下来的汤,可以重覆步骤17~20,不断地细分。
============================

大看看到没有,上面步骤17~20,其实就是〔三人分汤〕的步骤1~4。只要重覆这个步骤,就可以不断地把剩下的汤细分给四个人。光是靠步骤17~20,我们就可以作”无穷次地无嫉均分”,透过无穷次的细分,剩下的汤趋近於 0 。

问题是在〔三人分汤〕的题目里面,对於剩下的汤(”修剪”过程中倒回桶子的汤),我们能够找出”某甲”对”拿到A'的人”的〔绝对优势〕关系,因此再花一步就解决了。

但〔四人分汤〕的问题中,比较难以建立这种〔绝对优势〕的关系,因此我们要利用步骤3~步骤9来建立起 玩家1 对 玩家2 的〔绝对优势〕。

怎麼建立呢?很简单。

在第3步,玩家1 认为 B>A ,但 玩家2 认为 B=A 。这就是分歧,这也是建立〔绝对优势〕的基础。

只要 玩家1 觉得自己拿的比 玩家2 多,哪怕是一丝丝也好。接下来就不断重覆使用步骤17~20的无穷细分大法来处理剩下的残汤。经过无穷多次的细分,最终剩下的残汤肯定少於那”一丝丝”,因此 玩家1 就不会再想要与 玩家2 争夺那剩汤了。

步骤3~步骤9,简单说来如下:
<一> 玩家1 认为 B>A ,玩家2 认为 B=A ,这是分歧点,也是建立优势关系的基础。
<二> 让 玩家2 将 A 与 B 分别均分成为 n 份,对於 玩家2 而言每份都是一样大。
<三> 但 玩家1 却能够从 A 与 B 之中各自找出 3 份出来,使得 B1, B2, B3 严格大於 A1, A2, A3 ,然后再将 B1, B2, B3 修剪成为 B1 = B2 = B3
<四> 有了 A1~A3 与 B1~B3 这 6 份汤,再套用前述”无穷细分”的方法来分配给四个人--这样就建立起 玩家1 对於 玩家2 的优势了。

为什麼要分成 6 份呢?因为”无穷细分”的过程中,需要经过多次”修剪”,因此我们要保留足够的份数,这样才能保证最后轮到 玩家1 与 玩家2 来选汤的时候,一定还有”未被修剪过的 Ai 与 Bj”可以让他们无嫉地选,因此才要拆成 6 份之多--当然,随著人数的增加(五人?六人?),就要拆成更多份。。。

解释结束。

楼主 asmobia  发布于 2013-02-05 10:04:00 +0800 CST  
n人无嫉分配的解法。

第一章 微分法--不断地将汤进行无嫉分配,让残汤趋近任意小

先介绍〔微分法〕,〔微分法〕可以保证每一轮的分配都是无嫉分配,但同时每一轮分配之后都会剩下许多残汤;所以〔微分法〕只能够让残汤越分越少,但无法彻底把汤分光。

先将n个人编号为1~n。
<1>假设现在有X份汤(X是一个很大的数字,具体是多少后来会证明),让1号先选,这样1号不会嫉妒。

<2>在1号选汤之前,2号要先从X份汤之中挑出2份他认为最多的汤,并以其中较少的那1份当作标准、去”修剪”另1份较多的汤(”修剪”的意思是:把多出来的部分到回大汤锅之内等待下次重分)。
修剪完后,对於2号而言,有2份汤都是最大的,就算等会儿被1号挑走1份,轮到自己选的时候仍然可以拿到最大的汤(轮到2号选汤的时候,他必须优先选择自己修剪过的汤),所以2号不会嫉妒。

<3>在2号修剪汤之前,3号要先从X份汤之中挑出3份他认为最多的汤,并以其中较少的那1份当作标准、去”修剪”另2份较多的汤。
修剪完后,对於3号而言,有3份汤都是最大的,就算等会儿被2号修剪了1份、再被1号挑走1份,轮到自己选的时候仍然可以拿到最大的汤(轮到3号选汤的时候,他必须优先选择自己修剪过的汤),所以3号不会嫉妒。

<4>在3号修剪汤之前,4号要先从X份汤之中挑出5份他认为最多的汤,并以其中较少的那1份当作标准、去”修剪”另4份较多的汤。
修剪完后,对於4号而言,有5份汤都是最大的,就算等会儿被3号修剪了2份、再被2号修剪了1份、再被1号挑走1份,轮到自己选的时候仍然可以拿到最大的汤(轮到4号选汤的时候,他必须优先选择自己修剪过的汤),所以4号不会嫉妒。

f(1) = 1
=> 1号要选走1份汤
f(2) = f(1) + 1
=> 2号要考虑1号的选汤,再留1份给自己
f(3) = (f(2)-1) + f(1) + 1
=> 3号要考虑2号的修剪、1号的选汤,再留1份给自己
f(4) = (f(3)-1) + (f(2)-1) + f(1) + 1
=> 4号要考虑3号的修剪、2号的修剪、1号的选汤,再留1份给自己
f(5) = (f(4)-1) + (f(3)-1) + (f(2)-1) + f(1) + 1
=> 5号要考虑4号的修剪、3号的修剪、2号的修剪、1号的选汤,再留1份给自己
...
f(n) = ∑f(i),i=1~n, - (n-3) = 2^(n-2)+1

<5>n号要从X份汤之中,挑出份量最多的 2^(n-2)+1 份汤,并修剪成为全部相同,这样才能够放心地让后面的人修剪汤且先挑汤,故一开始第n号要把汤分为 2^(n-1)+1 份好进行分配。当然,n个人不可能分完 2^(n-1)+1 份汤,所以剩下来的残汤要倒回大汤锅之内,等待下一轮的分配。

<6>对於第n号而言,他每次负责分出 2^(n-2)+1 份汤,其中1份未经修剪的汤必定会被自己拿走。至於其他人的部分,由於可能会被修剪,况且修剪的多寡也不是第n号所能掌握的,因此第n号无法估算其他n-1个人究竟会分走多少汤。
故对於第n号而言,每一轮分配都能够把大汤锅里面的汤分掉至少 1/(2^(n-2)+1) 、剩下至多 2^(n-2)/(2^(n-2)+1)

只要不断重复著上述1~6的微分步骤,就可以在无嫉的前提之下将剩下的残汤缩小成为任意小--但任意小还是没有分完啊!所以我们需要动用另外一个叫做[绝对优势]的工具来终止无止尽的分配。






第二章 绝对优势--就算剩下的都归你,我也不嫉妒你

〔绝对优势〕的意思是说:”我认为我前面拿的东西比你前面拿的东西要多出太多了,因此就算剩下的一丝丝汤全都送给你,我也不会嫉妒你”。



楼主 asmobia  发布于 2013-03-13 19:09:00 +0800 CST  
在建立〔绝对优势〕之前,我们要先建立〔优势〕。怎麼建立〔优势〕呢?前面的”修剪”动作就是一个源头。

我认为两碗汤是相同的,但你认为要经过”修剪”之后两碗汤才会一样。那麼你”修剪”出来的部分X,就是我对你的〔优势〕,因为我认为你的那一碗汤比我的那一碗汤少了X。

有了〔优势X〕之后,再透过〔微分法〕缩减残汤,就可以把〔优势〕扩大成为〔绝对优势〕了。

依据〔微分法〕,每一轮分配都可以把残汤变小成为原本的 2^(n-2)/(2^(n-2)+1) ;等到残汤小於X的时候,我原先对你的〔优势〕就升级成为〔绝对优势〕了。此后就算你把残汤通通包走,我也不会愿意与你换汤--因为我前面的优势X比剩下的一丝丝残汤要大得多。

总结一下:
(A)所有”修剪”的动作,都是建立〔优势〕的源头。
(B)当某甲建立了对某乙的〔优势X〕之后,某甲可以透过重复的〔微分法〕缩减残汤,并建立起对某乙的〔绝对优势〕。

全部有n个人,所以最多共有 n*(n-1) 种〔绝对优势〕。请注意,〔绝对优势〕是纯粹主观的,因此某两个人可能互相觉得自己比对方有优势、也就是都认为对方拿的汤比自己少--这是完全成立的。

等到建立了一定数量的〔绝对优势〕之后,我们就可以进行〔最终分配〕,过程如下:

<1>任选一人将剩下的残汤均分为X份,其中X是”1~n的最小公倍数”。
<2>所有人都有投票权:如果你认为这X份是公平的,投赞成票,否则投反对票。
<3>投反对票的某人,如果对每位投赞成票的人都具有〔绝对优势〕,则该反对票失效。
<4>若所有反对票都失效(也就是说每位反对者都对所有赞成者具有〔绝对优势〕),那麼剩下的X份汤就让所有赞成者均分。由於X是1~n的最小公倍数,故必能均分。
<5>若还存在有效的反对票,那就代表我们还需要更多的〔绝对优势〕关系--不要担心,前面已经证明〔绝对优势〕的关系最多不会超过 n*(n-1) ,到了那个时候每张反对票都是无效的。

现在问题来了,虽然说”修剪”是建立〔优势〕的源头,但”修剪”并非必要的。。。理论上有可能〔微分法〕进行了一百轮也没出现过半次修剪动作,因此我们需要找到能够保证能够建立〔优势〕的机制。

幸好,上面〔最终分配〕的1~5点之中的”反对票”就是保证建立〔优势〕的源头。在〔最终分配〕的过程中,如果有人投反对票的话,那麼反对者必然认为某两杯汤不平均(a>b),而原分配者必然认为a=b,这就是建立〔优势〕的条件。






第三章 优势的源头--某甲认为a>b,某乙认为a=b

如果出现”某甲认为a>b,某乙认为a=b”,那麼进行以下操作:
<1>某甲决定一个很大的数字Y,Y > 2^(2n-6) + 2^(n-3) + 1 。然后由某乙将a与b都各自均分成为Y份,此时必须满足以下条件:当a与b各自被某乙分为Y份之后,某甲可以从a之中,去除掉最小的 2^(2n-6) 份,并使得剩下的a的部分仍然大於b。

<2>至於Y具体应该怎麼决定呢?很简单,假设某甲认为a-b=c>0,那麼某甲将Y设为 [2^(2n-6) + 2^(n-3) + 1] * (a/c) 必可符合条件。

<3>好,某乙将a与b各自均分成为Y份之后,由某甲选出a中最大的 2^(n-3)+1 份,以及b最小的 2^(n-3)+1 份,此时必然满足以下两者之一:
<3-1>a中最大的 2^(n-3)+1 份,每一份都严格大於b中最小的 2^(n-3)+1 任一份。
<3-2>某甲将a中最大的那1份再度拆成 2^(n-3)+1 份,使得每一份都严格大於b中最小的 2^(n-3)+1 任一份。
用反证法证明<3-1>与<3-2>必有一者成立:


楼主 asmobia  发布于 2013-03-13 19:09:00 +0800 CST  
===================================
假设<3-2>不成立,那麼a中最大的那份小於b中最小的 2^(n-3)+1 份的总和,故a中的任一份都小於b中的任意 2^(n-3)+1 份的总和,於是a中最大的 2^(n-3) 份的总和小於b中任意 [2^(n-3)+1] * 2^(n-3) = 2^(2n-6) + 2^(n-3) 份的总和。
假设<3-1>不成立,那麼a中排名第 2^(n-3)+1 大的那一份,必小於b中排名第 2^(n-3)+1 小的那一份。且可以推出a中排名第 2^(n-3)+j 大的那一份,必小於b中排名第 2^(n-3)+j 小的那一份,j ∈正整数。
若<3-2>与<3-1>同时不成立,则:
a中最大的 2^(n-3) 份的总和小於b中任意 2^(2n-6) + 2^(n-3) 份的总和
a中排名第 2^(n-3)+j 大的那份必小於b中排名第 2^(n-3)+j 小的那份,j∈正整数
故移除掉a中最小的 2^(2n-6) 份之后,剩下的a<b,违反<1>的条件,为不可能事件,故<3-2>与<3-1>必有一者成立。
===================================

<4>承上,某甲必能从a中找到最大的 2^(n-3)+1 份,使得每一份都严格大於b中最小的 2^(n-3)+1 份任一份。。。此时某家对a中最大的 2^(n-3)+1 份进行修剪,使得每一份一样大。

<5>将a中最大的 2^(n-3)+1 份与b中最小的 2^(n-3)+1 份摆在一起,让某甲与某乙之外的n-2个人进行〔微分〕。前面n-2个人完成〔微分〕后,由某甲在a的 2^(n-3)+1 份之中,选一个留给自己、再由某乙在b的 2^(n-3)+1 份之中,选一个留给自己。

<6>假设前面n-2人通通在a的 2^(n-3)+1 份之内进行修剪与挑选的话,那麼加上最后的某甲一共是n-1人,而 2^(n-3)+1 份正好可以完成n-1人的〔微分〕,故某甲必然可以拿到一个未被他人修剪过的汤;同理可证某乙也必能拿到一份未曾被人修剪过的汤。

<7>这样,所有人都是无嫉微分,但同时某甲必定认为自己对某乙有〔优势X〕,此后由某甲循环操作〔微分法〕,必能将残汤缩小至X以下,此时某甲就对某乙有〔绝对优势〕了。此时回归第二章的〔最终分配〕,由没有〔绝对优势〕的某乙来分汤,而某甲的反对票就可以忽略不算了。。。如果最后没有任何反对票,那麼依据第二章〔最终分配〕的办法就可以结束了;如果不幸还有有效的反对票的话,那必然存在”某丙认为a>b,某丁认为a=b”的情况,就继续回到本章的开始,建立起某丙对某丁的〔绝对优势〕。。。

<8>过程中如果有任何”修剪”的动作,都可以顺便配合”微分法”来建立〔绝对优势〕,这样可以加快分配的进程。

楼主 asmobia  发布于 2013-03-13 19:09:00 +0800 CST  

楼主:asmobia

字数:4068

发表时间:2013-01-27 08:03:00 +0800 CST

更新时间:2021-01-13 16:53:03 +0800 CST

评论数:123条评论

帖子来源:百度贴吧  访问原帖

 

热门帖子

随机列表

大家在看