有这样一道题:
波斯公主从100个男人中选驸马,从1号开始如果公主不满意就会PASS掉,公主不可以回头再找被PASS的男人,如果最后公主也没有选出来就要选最后一个100号为驸马。问公主如何才能选出最帅的男人做驸马?
这是著名的选驸马理论,用数学的方式最优选法:先PASS掉前100/e个男人,e≈2.72,即前37个要PASS掉,但记录出前37中最帅的,公主从38号开始选,遇到比前37号中最帅的那个就选作驸马,如果没有比前37中最帅还帅的就选第100号。这个最优解中,公主有大约40%的概率选出最帅的男人,是所有方法中概率最高的。
那么问题来了,如果我们作为被选者,我们要站在几号才有最高的被选率呢?38号或许是个不错的选择,粗略一想,只要比前37号最帅的帅就可以被选中了,而越往后前面出现的人越多概率就越小。但38号真的是最好的号码吗?38号被选中的概率有多大呢?第100号貌似也是个不错的选择吧?
38号的被选概率:
1、 38号的帅值是随机的,那么他帅值100的概率1/100,被选的概率就是1/100。
2、 38号帅值是99的概率是1%。要被选就要帅值100的那个在后面的62个号中,这个概率是62%。38号被选概率为1%*62%。
3、 38号帅值是98的概率1%,帅值100和帅值99的在后62个中的概率为62%*61/99。38号被选概率为1%*62/100*61/99。
4、……
……
……
63、 38号的帅值是38,天啊,刚好需要前37个都是比自己丑的,概率为1%*62/100*61/99*……*1/39
将所有概率相加,通过计算机计算为1.59%。
所以看似概率很高的38号被选中的概率为1.59%,那么100号呢,只要帅值为100的在前37号中就能保证选到100号,简单一想这个概率大约为37%(因为可能自己是帅值100,所以是大约,没细算)……这么看来被公主看中的概率实在小,公主最后挑累了又不得不选一个的时候选择了不是最优的第100号,看来一个人出现的timing很重要呐!
综上,是我出现的timing不对才会不能在一起吧,我一厢情愿的这么想着,如果感情也是一道数学题目,我的题目是否有最优解呢?最优解又是什么呢?解题步骤又是怎样的呢?纵使掌握最优解的解法又能得到最优解吗?