(更新至5/5.)
1.
熟知的问题,有些细节根据定义不同差异太多..举些栗子..
某人"满意"可以指"认为自己最多",也可以指"认为自己达到均值".
像两人分,一人分一人挑就可以认为两个都满足.
下面说些N人的:(还是说成切蛋糕顺口..)
- 不断将液体倒到某杯中/刀在蛋糕上逐渐移动/...,直到有人认为到均值喊停,分给ta.
这个可以符合"达到均值"的要求,但不符合"自己最多"的要求.同时,需要额外的设定:分出的一部分的数量可以连续变化.(关于这点..这么说吧..通常是假设要多少就能切出多少,但没有假设这个数量可以连续变化.) - 另一个方法,从整块开始,第一人到最后一人依次看剩的是否够均值,若有多则削剩均值.最后,这块归最后一个动的人所有.
同样,这个也只是符合"认为自己达到均值"而不符合"认为自己最多". - 再说一个方法,也是"达到均值"的版本.
第一人分成2份,第二人选认为不少的一份.此时两人都认为自己有至少1/2.
前两人将自己的分成3份,第三人从两人处各取一份,这样三人都认为自己至少有1/3.
前三人将自己的分成4份,第四人从三人处各取一份,这样三人都认为自己至少有1/4.
...
重复N次即可. - 最后再说一个三人的免嫉妒分割 (envy-free division)(也就是"认为自己最多"的版本)的方法Selfridge-Conway算法.比较长,直接复制粘贴吧..反正估计没多少人细看....
首先，A 把蛋糕分成三等份（当然是按照自己的看法来分的，后面提到的切分、选取也都是这样）。如果 B 认为这三块蛋糕中较大的两块是一样大的，那么按照 C、B、A 的顺序依次选取蛋糕，问题就解决了。麻烦就麻烦在 B 认为较大的两块蛋糕不一样大的情况。此时，B 就把最大的那块蛋糕的其中一小部分切下来，让剩余的部分和第二大的蛋糕一样大。被切除的部分暂时扔在一旁，在第二轮分割时再来处理。接下来，按照 C、B、A 的顺序依次选蛋糕，但有一个限制：如果 C 没有选那块被修剪过的蛋糕，B 就必须选它。
这样，三人就各分得了一块蛋糕。由于 A 是切蛋糕的人，对于他来说拿到哪一块都一样，因此 A 不会嫉妒别人。由于 B 选取的是两个较大块中的一个，因此 B 也不会嫉妒别人。由于 C 是第一个选蛋糕的，显然他也不会嫉妒别人。因此，就目前来说，三个人之间是不会有嫉妒发生的。
但是，还有一小块被切除的部分没分完，因此分割流程进入第二轮。
在 B 和 C 之间，一定有一个人选择了那块被修剪过的蛋糕。不妨把这个人重新记作 X，另一个人就记作 Y。让 Y 把最后那一小块分成三等份，按照 X、A、Y 的顺序依次挑选蛋糕，结束第二轮流程。这一轮结束后，每个人都又得到了一小块蛋糕。由于 X 是第一个选蛋糕的人，X 显然不会嫉妒别人；由于 Y 是分蛋糕的人，Y 也不会嫉妒别人。由于 A 比 Y 先选，A 不会嫉妒 Y。最后，A 也是不会嫉妒 X 的，因为即使 X 拥有了第二轮中的全部蛋糕，X 手里的蛋糕加起来也只是第一轮开始时 A 等分出来的其中一块蛋糕，这是不可能超过 A 的。这就说明了，三个人之间仍然不会有嫉妒发生，Selfridge-Conway 算法的确满足免嫉妒条件。
这就说完了.至于免嫉妒分割的N人版本(N>3),还没有结论.记得在猴子的贴里这些也都说过了.
2.
熟知的二进制.
首先要假设的是我们的做法:取若干瓶各少许混合给一只老鼠喝,对不同老鼠选法不同,需要的是设计选法使得能从死了哪些老鼠判断出哪瓶有毒.
显然,总共N只老鼠,每只都有死和不死两种可能,那么总共至多能分辨2^N种可能性,也就是酒的瓶数不超过2^N.
而熟知这个界是可以达到的,而且做法唯一(或者说等价):给酒编号0到2^N-1,对其中每个数,二进表示中哪些数位是1,就给哪些老鼠喝;也就是说,将这2^N个数中某位为1的所有酒(取少许)混合后给对应的老鼠喝.
显然,老鼠死说明毒酒此位为1,于是用01表示老鼠是否死了,串起来就是毒酒编号.
ps.这里N=16,那么答案是2^16=65536.
3.
再一次,题目叙述不清.明明问的是有多少种几种坐法,答案就是N!.但是又明确表示"连续两回合不能坐同一张椅子",全然看不懂这和问题有啥关系.(应该说,我只能明确看出题目肯定有表述问题.)
反正据我猜测,出题人的意思可能是"某一轮都坐成功了,问下一轮有多少坐法".
如果真的是这个意思,那这就是熟知的bernoulli错排问题/放错信笺问题/...,答案是N!(1/2!-1/3!+1/4!-...±1/N!),证明的话直接容斥原理然后化简下就好了,不赘述.也有递推的版本,同样,反正想知道的问度娘.
ps.这里N=8,那么答案是14833.
ps2.看到lz前边认为正确的答案也是14833,说明我这个题意猜测应该是对的.
4.
熟知,八卦贯石.
挂八卦贯石,杀.若不护驾直接死,否则二位郭嘉先护驾,开八卦,拿天妒牌和八卦两张用贯石补中.
甄姬忠臣只能护驾和无懈而不能给桃,故对贯石补中没办法;没用锦囊,故无懈也没用.
5.
熟知的结论是98,0,1,0,1,也就是能分到98.
如下考虑:如果仅剩45两人,4全给4自己然后自己同意即可,所以123死的话5啥都得不到.
所以3提方案的时候无论如何2会反对,而只要给5东西5就会同意.
...
以下同理,略.
刚才没看清,现在看清了.又有表述问题..这次我不猜原意了..
第一句是"当且仅当达到半数或者超过半数的人同意时"
第二句是"当且仅当超过半数的人同意时"
差异这么大,还怎么以次类推??
好吧..题目改了..那就没事了..
================ 以上据说只是背景的不是题目的 ================
================ 以下的才是题目的 ================
我又想吐槽题目了..如果三个人的方案都没通过怎么办?连这都没提到还让人怎么玩??
"如果违反任何协议就会损失300枚金币的公证处门前"只是描述那个公证处这样而已,跟三人有个喵关系吖??
退一万步讲,就算是跟三人有关系,那三人现在又不是在定啥协议,结果还是木有个喵关系吖?!
再退一万步讲,如果这些 提方案 算是协议的话,那为了用这条件,是不是说"他啥都不分给我,可我已经同意了.可我突然又暴起弄死了他们俩抢走了那300块钱,所以我算是'违反了协议',所以300块钱又要被没收"??
既然lz提到liar game..大概也许想学里头那样玩支票吧..
hmm..汇报最新进展..私下已使用协议将题目玩崩....随便搞几个自涉就悖论了....还有什么"支持我我保证不打死你""支持我我做你仆人"或者简单的公证个欠条什么的..也完全无法衡量不同方案了吖- -
本帖最后由 天马行空 于 2014-11-13 16:08 编辑 |
