[拜托了学姐]海盗配对问题（规则有更新）
假设有26个海盗，奇数为女性，偶数为男性，按编号依次为A子，B君，C子，...Z君他们之间的关系很JB乱，在无数次的争吵、斗智、好船之后，他们一致同意进行固定配对。先由A子来决定配对方案，如果方案不能被超过半数的人（提案人本身不参与投票）赞同，则A子会掉头，接下来由B君分配；同样的，B君如果得不到半数人以上的支持则会被铝热剂烧死，以此类推。
已知条件如下：
所有海盗全都聪明绝顶且无比理性，会作出使自己的利益最大化的选择，也能够根据这样的思路对别人的方案进行推断。
海盗们之间的关系如下：A子和B君相互爱慕，C子喜欢B君，D君喜欢C子……以此类推；而B君将C子作为备胎，C子将D君作为备胎……也以此类推。
海盗们“利益”的优先程度由高至低如下，为了优先级高的利益可以放弃较低级别的利益：
保住自己的性命
保住自己爱慕之人的性命
分组中存在自己爱慕之人
分组中的同性尽可能少
分组中存在自己的备胎
分组中的异性尽可能多
分组数尽可能多（虽然自己开了后宫/逆后宫，但不允许别人开 ）
尽可能多让别人掉头/烧死
那么，假如你是A子，你会怎样分配呢 引用楼主passerby0427于2012-03-20 16:20发表的 [拜托了学姐]海盗配对问题 :
假设有26个海盗，奇数为男性，偶数为女性，按编号依次为A子，B君，C子，...Z君
奇偶反了？ 死定了！ 引用第2楼zorya于2012-03-20 16:27发表的:
奇偶反了？ images/back.gif
一开始写反了，已修正 本来按标准方法应该是逆推的，但是一开始A子只要提议AB, CD, ... , YZ这样的方案，这样B肯定同意，其余24人也应该有一半同意不就直接通过了么？
条件里面并没有“在保住自己性命的情况下，尽可能让别人多死几个”这样的准则 这根本不是分金问题 A和B，C和D，E和F.............这样不就是一定有14人满意了么 这个问题和这个题材匹配得太差,打回重来 其实进行逆推的话，前几步还是有点意思的。
不过有一些细节还需要补充：
比如，提案人自己不参加投票
自己喜欢的人的生死是否需要考虑？
在已经可以获得和自己喜欢的人配对的前提下，是否倾向于获得更多的异性配偶
这些都必须确定才能进行严密的推理。 引用第5楼zorya于2012-03-20 16:35发表的:
本来按标准方法应该是逆推的，但是一开始A子只要提议AB, CD, ... , YZ这样的方案，这样B肯定同意，其余24人也应该有一半同意不就直接通过了么？
条件里面并没有“在保住自己性命的情况下，尽可能让别人多死几个”这样的准则 images/back.gif
不一定的。对于5人来说，A子可能支持CD或DE，也就是说C子或E子都有可能苦逼（跟剧情好像 ）
那么对于6人来说，给予D君或F君（人物顺移）一个确凿的不会打光棍的未来更好，尤其是对于只要不同意就必定得不到喜欢的人的D君来说，因此可以将D君收入逆后宫（喂，节操呢 ）
不过规则的确要改一改，多谢 引用第10楼zorya于2012-03-20 16:44发表的:
其实进行逆推的话，前几步还是有点意思的。
不过有一些细节还需要补充：
比如，提案人自己不参加投票
自己喜欢的人的生死是否需要考虑？
在已经可以获得和自己喜欢的人配对的前提下，是否倾向于获得更多的异性配偶
....... images/back.gif
自己喜欢的人死了，自己当然就分配不到，这是仅次于自己死了的第二坏的结果。
设定是都想开后宫（逆后宫）的狗男女们 引用第7楼fsckamui于2012-03-20 16:39发表的:
A和B，C和D，E和F.............这样不就是一定有14人满意了么 images/back.gif
其实未必的。
如果按原始的海盗问题，还有一条我前面说的“海盗倾向于让其他海盗去死”，所以到何种程度才算满意要看条件怎么设定。
只剩XYZ或者YZ时，Z同样能够保证一定能Y配对，所以如果没有更有利的分配方案（或者之后那个人一定会被通过的方案对Z不利），Z可以一直反对。 这不是分金问题。 引用第12楼passerby0427于2012-03-20 16:50发表的:
自己喜欢的人死了，自己当然就分配不到，这是仅次于自己死了的第二坏的结果。
....... images/back.gif
这还是有区别的。
比如自己喜欢的人提出的方案让你光棍，你是否也无条件接收？
投赞同票自己仍然是光棍一个，但是喜欢的人可以活下来。
投反对票自己可能得到一个其他的配偶。
那么这两者哪个的优先度更高？是喜欢的人活下来自己光棍，还是喜欢人死了但是自己有配偶？ 引用第17楼zorya于2012-03-20 17:07发表的:
这还是有区别的。
比如自己喜欢的人提出的方案让你光棍，你是否也无条件接收？
投赞同票自己仍然是光棍一个，但是喜欢的人可以活下来。
....... images/back.gif
你若安好，便是晴天
不，果然还是设定成“我得不到的谁也别想得到”比较好吗 分金问题的"金"是不参与的,所以这个不是分金问题
Re:回 16楼(zorya) 的帖子
引用第19楼fescn3于2012-03-20 17:16发表的 回 16楼(zorya) 的帖子 :不会出现这个情况的啦。因为非A子的情况下，提案人喜欢的人已经死了。那么他、她分配得到的人对提案人本身是没有区别的。
如果让喜欢自己人光棍的话，而自己不是光棍的话。那么就会同时损失了三票。那么就死定了。
为了能生存，那么选择喜欢自己的人就是必然的了。。。 images/back.gif
不是必然的啊，比如我们从最初开始倒推。
只剩YZ
分配方案只有一个，而且Z肯定同意。
只剩XYZ
X提任何方案Z都会反对，X死定了
只剩WXYZ
W提任何方案X都会同意
Y只要能得到X就会同意
所以Z的票可以无视
W的最佳方案为： WZ, XY
只剩VWXYZ
V在4个人中要获得3个人的支持，
那么有两种不同的方案：
1.VWX， Y-Z
2.VZ, WXY （EDIT：弄错了，其实这个方案是不能通过的，因为Y不会同意，而且VZ是同性=v=。不过我觉得这个条件仍然要确定才更有利于推理。）
如果W是无条件同意喜欢的人的方案，那么2成立，而且这个方案对V更有利（可以独享配偶）
如果W不是无条件同意喜欢的人的方案（也就是说不管喜欢的人死活，只比较可能获得结果的好坏），反对方案2由自己来提案能够独享配偶要更好一些。
这种设定下，方案2不成立。
这一点差异就决定了V是应该提出方案1还是2。 只烧男的，不烧女的？
那最后剩下的那个男的可以直接后宫？
我lx的aki不可能这么聪明！ 这其实和分金有点类似，并不是那么简单就能获得一半人的支持的。
拿Z来说，即使前面的人提出了YZ这种方案，为了得到Y，最彻底的方法就是把X消灭。如果前面没有想留下来的人，就可以一直反对到最后。但是这不可能，因为如果只有留到XYZ，X为了保命提出XY配对，从而超过一半的支持率而通过。因此Z会为了消灭尽量多的其它人（最次条件）而一直反对，一直到中后期才考虑同意前面提出的有YZ的配对方案。
同理，越往后的越难说服，而越往前的即使没有分配，也会为了保命而同意。
我感觉机会是一半一半的，能不能活下来只能看A的说服力和临场发挥了。 还有，想一配多开后宫不可能实现，这种方案只会导致多数人反对，所以一一配对是基础。
另外，某些人你们好过分啊。在下至少也是经历过试召战争，带过队伍，指挥过FFF团小分队的，而且经历过众人围堵生活下来的，这种思考能力肯定不在话下。都说了只是不擅长考试而已！才不是什么笨蛋！！ 引用第23楼吉井明久于2012-03-20 17:39发表的:
这其实和分金有点类似，并不是那么简单就能获得一半人的支持的。
拿Z来说，即使前面的人提出了YZ这种方案，为了得到Y，最彻底的方法就是把X消灭。如果前面没有想留下来的人，就可以一直反对到最后。但是这不可能，因为如果只有留到XYZ，X为了保命提出XY配对，从而超过一半的支持率而通过。因此Z会为了消灭尽量多的其它人（最次条件）而一直反对，一直到中后期才考虑同意前面提出的有YZ的配对方案。
同理，越往后的越难说服，而越往前的即使没有分配，也会为了保命而同意。
我感觉机会是一半一半的，能不能活下来只能看A的说服力和临场发挥了。 images/back.gif
靠说服力什么的根本就不是智力推理题了……
而且明⑨你采用条件是“提案者自己也可以投票”，跟我用的不同。 引用第27楼吉井明久于2012-03-20 18:04发表的:
还有，想一配多开后宫不可能实现，这种方案只会导致多数人反对，所以一一配对是基础。
另外，某些人你们好过分啊。在下至少也是经历过试召战争，带过队伍，指挥过FFF团小分队的，而且经历过众人围堵生活下来的，这种思考能力肯定不在话下。都说了只是不擅长考试而已！才不是什么笨蛋！！
images/back.gif
未必。1+2这种配对是可以的，有时候甚至是必须的。 楼主说的是超过半数人同意，没有说限定在其它人中，所以我把提案人也算进去了。
引用第29楼zorya于2012-03-20 18:19发表的 :
未必。1+2这种配对是可以的，有时候甚至是必须的。 images/back.gif
我的意思是一对多不利因素会增加，如果想开后宫(>3)基本不可能，应该以一一为基础。
像楼上的某个3个人一组的方案，一个人要分给两个，先不说最前面的几组，后面几组多半的人大多不会同意。
越到后面机会越大，何必同意和其它人分一个呢。
Re:回 21楼(zorya) 的帖子
引用第30楼fescn3于2012-03-20 18:29发表的 回 21楼(zorya) 的帖子 :其实WXY这个组合中Y不是一定反对的。因为单纯的XY配对会被Z反对，最后X只有死路一条，那么为了保证X的生存，Y会作出让步，那么WXY也是可行的。
以此类推，可以得出如果是“123”的情况下，3会为了保证2的生存而让步。因为如果到了2提案的时候，2一样会提出3P作为最大化的方案（当总人数大于等于6的时候），那么这个对她来说是没有差别的。所以123的组合，3会同意，只有1会反对。
所以最后26人的情况下，提案应该是这样的：
....... images/back.gif
蓝字部分Y确实会同意WXY的方案，但是对于W本人来说，WZ, XY的方案更有利。
红字部分是有差别的，同样是3个人，123的情况，和234的情况，对于3来说显然是后者更有利。
所以这个问题应该跟原始的海盗问题一样，从后面一步一步的逆推，而不能简单的“觉得”有哪些人会同意或者反对某个方案。
实际上每个人选择的标准应该是：如果能获得比下一个一定会通过的提案更好的分配方案，那么就同意，否则就反对。 引用第31楼吉井明久于2012-03-20 19:01发表的:
楼主说的是超过半数人同意，没有说限定在其它人中，所以我把提案人也算进去了。
我的意思是一对多不利因素会增加，如果想开后宫(>3)基本不可能，应该以一一为基础。
像楼上的某个3个人一组的方案，一个人要分给两个，先不说最前面的几组，后面几组多半的人大多不会同意。
....... images/back.gif
你的这个想法太想当然了一点。实际上由于设定中喜欢的方向是单向的，连续3人一组反而有三分之二的人可以跟喜欢的人在一起，2人一组反而只有一半的人会跟喜欢的人在一起。这类问题就是一步一步推演出来的，没有什么“多半”之类的推测。
Re:回 32楼(zorya) 的帖子
引用第34楼fescn3于2012-03-20 23:07发表的 回 32楼(zorya) 的帖子 :所以W会反对啊。我没说W会赞成。但W赞成不能动摇结果。
这个和海盗分金最不同的是，这里分的是人，是投票者本身，而且这些人对不同的人的价值是不相同的。海盗问题，前面的海盗越是死，后面的越是有利，但这个前面的死了，后面怎么分配都是亏了。
另外，WZ、XY这个方案是没有意义的。因为对W来说最有意义的方案是VW+、其次是VW、再次是UVW，而这三个都不是W可以提案的。
....... images/back.gif
在轮到W提案的时候W不会选择WXY，Z而是会选择WZ、XY。
几乎轮到每一个人提案的时候，都不会是自己最想要的提案，因为除了A之外，喜欢的人都已经死了。
这个问题强调的是这些海盗每一个都很聪明而且会分析其他海盗的行为模式。所以只能从最后的情况进行一步一步的逆推。
WZ、XY这个方案就是在轮到W提案时W的最佳选择，而这个选择决定了W之前的人将会做出怎么样的提案以及选择。
所以对于这个问题是“有意义的”。 引用第28楼zorya于2012-03-20 18:06发表的:
靠说服力什么的根本就不是智力推理题了……
而且明⑨你采用条件是“提案者自己也可以投票”，跟我用的不同。 images/back.gif
呃，考虑了一下觉得还是提案人不参与投票比较好
规则已补充更新 关键推论：第二位的人会无条件同意第一位的主张；
YZ，分组为（YZ）；
XYZ，参照上种情况，X必死，无解；（裸妹子的黑化 ）
WXYZ，为了保住X的性命，Y会无条件同意W的一切主张，分组（WXZ），（Y）；（主角人参赢家， 友为救蓝毛而苦逼）
VWXYZ，只要Y不打光棍就会同意，解为（VW），（YZ），（X）——也就是说果然蓝毛是苦逼
下面的没有仔细推敲：
（UVZ），（W），（XY）
（TUW），（V），（XYZ）
（STVZ），（U），（WX），（Y）
（RSUY），（T），（VW），（X），（Z）
（QRTXZ），（S），（UV），（W），（Y）
（PQSWY），（R），（TU），（V），（X），（Z）
……
差不多有规律了呢 引用第37楼passerby0427于2012-03-21 02:13发表的:
下面的没有仔细推敲：
（UVZ），（W），（XY）
（TUW），（V），（XYZ）
....... images/back.gif
前面都非常完美
但是到推敲的第二步貌似有异议...
我个人的方案是
（UVZ），（W），（XY）
（TUY），（VZ），（WX）
产生这种解的原因是没有照顺推思路由于V一定反对且是异性所以就让他苦逼...
而这里异议比较大的是Z君, Z君投赞同的原因是虽然V子和他毫无关系, 但是和上一种情况比好歹没有其他异性...
同时UWX一定会赞同此方案 所以最终4:2投票通过
相对（TUW），（V），（XYZ）, 这种方案排除了另一组逆后宫 而又让Z很苦逼地和毫无相干的V分到一组
虽然双后宫的方案可以让V更苦逼, 不过我觉得322这样似乎更没节操点...
页:
[1]
2