海盗分金问题

首先看看问题的题目,10个海盗分100个金,规则如下,最厉害的海盗提出分的方案,如果分金方案获得50%或以上通过(包括自己的投票),则按照此方案分,否则该海盗被扔进海,然后由第二强的海盗提出分金方案,重复整个过程,直到得出方案为止。

问题本身还有一些假设前提,所有海盗是理性的,也就是说他们最看中的是自己的生命,其次是钱。如果能够保命的情况下,自己分得越多越好。

现在问题是问,到底最厉害的海盗应该提出一个怎样的方案,才能既保证自己的安全,又能尽可能多地获得金呢?

这个问题是典型的很难入手的题目之一 ,因为就算你真的为最厉害的海盗提出了一个方案,比如每人平均分得10金这样的方案,我们也很难论证到底谁会投赞成票,谁会投反对票,就是他们的理性很难衡量,比如我们可能会想,很多海盗可能不会为这个方案投赞成票,因为我们认为他们可能会想,如果把现在最厉害的海盗弄死,那么剩下的人瓜分的钱就会更多。这道题的模型是加州大学的教授提出来的,典型的难以入手的题目。下面我们来一起探讨这个问题。

这道题目解决的方法之一是倒推法,我们从最弱的海盗开始编号。假如现在只有两个海盗1号和2号,2号比1号强,所以由2号提出解决方案,因为2号肯定会投自己的票,所以赞成票肯定不少于50%,因此2号必定安全,所以他的最有利方案是自己独占100金,给1号0金。

好了,那假如现在还有一个3号海盗,他知道2号肯定投反对票,因为如果他3号死了,2号就能够独占100金,他为了自己不死,一定要1号投赞成票才行,所以他提出的方案是他自己3号99金,1号1金。1号肯定会赞成的,因为他如果投反对票,剩下两人的时候,自己一分钱也拿不到,投了赞成票,至少有1金。

继续倒推,4号要收买2号帮自己,他提出的方案是4号99金,2号1金,因为如果4号死了,像上面提到的三个人的情况,2号什么也拿不到,但现在投赞成票至少获得1金。后面的同样道理,奇数号的人要收买奇数号的人帮自己,偶数号的人会收买偶数号的人帮自己。所以只有10个人的时候,10号提出的方案是自己96金,2、4、6、8号各1金,2、4、6、8号肯定投赞成票,因为如果10号死了,由9号提出方案,他们一分钱也拿不到。

问题似乎解决了,其实这个模型是如此深奥,试想一下如果超过了200号,那么用来收买的钱都不够了,怎么办,这个问题以后有机会再继续探讨。

Advertisements

Bloxorz

Bloxorz貌似也是一个flash game,而且彻底是一个智力游戏,它的创意之处在于翻箱子,一看就知道是以前推箱子的继承,想不到改变了玩法之后竟然如此有趣,可以横着滚,也可以竖着滚,只要能够达到目的,而且它里面还有很多东西要思考,比如有很多桥的开关,有的只要横着滚过去就可以触动开关,有些则要竖着站起来才可以触发。

地址在这里,Bloxorz

Bloxorz

这个游戏关键的地方在于横着滚调整位置,作者出的关也很典型,不错,^_^

The End of Final Exam

Today I had the last exam of this term, which is Computer Graphics. Thanks to the Teacher Wang, I think I can pass the exam bacause she didn’t baffle us.

So tonigth, I can go to South Campus with others. There, we gave our seniors a warm send-off party. The party was excellent. All people were lost in it and had a good night. Many interesting games were held in the party. A lot of great seniors gave our talks which make me deeply impressed. I only can say I learn a lot and I want to be the one like them. I will pratice hard to finish my objective. The party is so good that my tireness was all gone. My energy is full now, haha…

还有一科

还有一科就考完了,哈哈,今天决定用中文写blog,因为等一会还要复习呢。

今天可以说是一个阴转多云的天气,昨晚12点怀着极其不安的心情上床睡觉,因为数据库还没看完,如果按老师的提纲,起码还有3大章内容没复习,而且都是新内容,以前又没学过。其实都怪自己平时上课睡觉而已。直到今天早上考数字图像处理时候,还念念不忘数据库。到了中午也没有太多时间了,结果还是战战兢兢地去了。卷子发下来,忽然发现老师是一个大好人。就这样,算是跨过一步了。

刚才玩了一盘TD,第三次玩Medium,终于通关50关了,不过现在还是好好收拾心情,准备明天最后一科考试,而且考完可以去南校区cisco-team玩游戏了,^_^

Tower Defense

Tower Defense is a very interesting flash game, a used-head game. There are five to seven weapons we can use to defense the enemies.

Tower Defense

The newest version of the game is 1.5 and more weapons added to the game. I like it very much although it made my CPU too hot to warn.

My First Post

It is in the process of Final Exam. But today’s morning I just had a exam of Computer Architechture, so this afternoon I didn’t go to review and another reason is it’s so hot today and I’m lazy.

But the afternoon, I remember that I have learned a skill to surf the nterent by Tor, so I use it to go to wordpress.com, and luckily I succeeded.

First Post

Now I must go to the class. Next time I will introduce a girl Vera.