Question

微软面试题

曼哈顿有多少路灯？

Answer 1

5个囚犯，分别按1-5号在装有100颗绿豆的麻袋抓绿豆，
规定每人至少抓一颗，而抓得最多和最少的人将被处死，
而且，他们之间不能交流，但在抓的时候，可以摸出剩下的豆子数
。问他们中谁的存活几率最大？提示：
1，他们都是很聪明的人
2，他们的原则是先求保命，再去多杀人
3，100颗不必都分完
4，若有重复的情况，则也算最大或最小，一并处死
1、至少要抓1颗
2、数量最多=死 数量最少=死 数量相等=死
3、他们都是很聪明的人
4、先保命，再杀人
5、100颗不必全分完
问：5人中谁的存活几率最大？
思路：
结局一、顽强的挣扎。（意思是说，他们5人无论是谁，都想在分抓绿豆的过程中，侥幸得以存活，因此，都会顽强的绞尽脑汁去挣扎去给自己一个天衣无缝的选择）
在前提条件的控制下：
1号囚犯：拥有首先选择的权利。
但1号囚犯的缺点是：将自己所抓的数量毫无保留的暴露在2号囚犯面前。（这一点1号囚犯也心知肚明）那么，1号囚犯清楚的明白，轮到2号囚犯去选择的时候，他们后面还有3名囚犯，也就是存在着3个未知数，在还有3个未知数的情况下，2号囚犯一定不会选择和自己拿的一样多，假如自己拿了X颗，那么2号囚犯，必定只可能有两种选择，要么是X+1颗，要么是X-1颗。因为2号囚犯绝对不会允许自己所抓的颗数，和1号囚犯所抓的颗数中间存在夹层，也就是说，1号囚犯和2号囚犯分别所抓的颗数，是2个连续的自然数。一个奇数，一个偶数。
那么，1号囚犯会选择几呢？100颗豆子五个人分，中间平均数是20。
假设1：五个人聪明程度一样。
1号囚犯选择20颗，2号一摸，发现剩下80颗，就知道1号囚犯拿了20颗。那么，2号的选择有：19 21 两种。也就是说，1号囚犯的选择会影响到2号囚犯的选择。如果2号选了19颗，那么，轮到3号抓的时候，就知道，前面2个人一共抓了39颗。39颗豆子两个人分，根据前提条件的限制，只可能是20和19。那么究竟谁是20？谁是19呢？3号会想：“如果5个人都抓了20颗，大家全死！”这句话，每个人都知道。那么，假如1号抓了20，2号必定是19，因为3号认为2号不可能抓21，原因有2点，原因一，因为只要2号抓19，那么后面还有3个未知数，也许就有比19小的，比如18。所以3号认为2号抓19对自己最有利，原因二，如果2号抓21，那么2号应该明白，轮到3号的时候，3号会清楚的知道前面2人一共抓了41颗，那么只可能是20和21，不可能是19和22，因为无论是1号还是2号，都不可能允许2个人抓的数字中间有夹层。所以，3号一定可以推断出来，前面2个数字是20和21，那么3号无论如何也不会选22，3号只会选19对自己最有利可是这样一来，对2号自己来说，就不利了，所以，如果1号抓20，那么2号一定是19。以上分析结果，相信3号一定分析的出来，那么1号拿了20，2号拿了19，3号会拿几呢？如果是你，你会拿几？20？不会。19？不会。21？不会。只会是18。那么，假如1号拿了20，2号同样也会有以上分析，2号知道，自己拿19颗对自己最有利，而且2号也知道3号知道自己会拿19，那么3号会拿18。那么，1号同样也会有以上分析，因此，在1号决定了要拿20颗的时候，1号就清楚的分析出2号会拿19，3号会拿18。也就是说，1号2号3号三个人都知道彼此分别拿了多少。现在轮到4号，4号一摸，发现，还剩下43颗豆子，前面三人一共拿了57颗，根据以上分析，4号很简单就可以推出1号拿了20，2号拿了19，3号拿了18。那么4号会拿几呢？我认为，4号会拿17颗。因为，这样可以保证不和前面任何一个人拿的一样多。那么，我们先不看5号，先看看前4个人分别拿了多少，依次是：20 19 18 17 在这四个数字中，1号和4号是暂时的死亡对象，可是，还有5号没有拿，但如果以上拿法成为现实，那么很显然，5号已经是必死无疑了。那么，5号会想，反正横竖我都是死，不如拉两个和我一起死，那么，5号的选择只可能是20 19 18 17 这四个数字中的其中一个。为什么不可能是21呢，因为如果5号拿了21，那么将会有3个人同时存活，那么不符合尽可能多的杀人的前提条件了，如果5号在20-17这4个数字中选择，当5号拿20，会有3个人死。当5号拿19，会有4个人死。当5号拿18，也会有4个人死。当5号拿17，会有3个人死。总结一下，当5号拿20和17会有3个人死，当5号拿19和18，会有4个人死。这样，为了尽可能多的杀人，5号的选择，只可能是19或者18。这样比较符合条件。因此，当1号决定拿20颗的时候，5号就只能在20-17中间选择一个，那么，如果5号选了19，1号最大，1号是死；如果5号选了18，1号最大，1号是死，如果5号选了17，1号最大，1号是死。如果5号选20，和1号一样多，1号还是死。那么通过以上分析，1号选20颗必然是死。
因此，1号不会选20。可是，无论1号选几，2号都会比1号少选一颗，3号都会比2号少选一颗，4号都会比三号少选一颗。那么，又轮到了5号，假如1号拿了X颗，2号一定是X-1，3号一定是X-2，4号一定是X-3。，那么，5号在必死的前提下了为了尽可能多的拉人一起死，那么，5号的选择只可能是X、X-1、X-2、X-3。根据前面的分析，5号的选择，只可能是X-1和X-2两种。
所以，无论1号选的X究竟是几，1号都是必死的。题目问的是，谁的存活几率最大，那么1号囚犯的存活几率为0。
那么，继续，我们来看囚犯2，不管1号拿了几，囚犯2号只要拿X-1颗，那么，轮到5号的时候，在5号所有的2个选择中，当5号有且仅有拿到X-1颗，也就是当5号拿的和2号一样多的时候，2号才会死，5号拿X-2这个选择的时候，2号会活。那么2号的存活几率是50%。
再看3号，同眼道理，当5号有且仅有拿到X-2颗，也就是当5号拿的和3号一样多的时候，3号才会死，5号拿X-1这个选择的时候，3也号会活。那么3号的存活几率也是50%。
再看4号，前面分析了，5号只会选择19和18两个数字，那么也就是X-1和X-2两种，换句话说，5号不可能拿的和4号相等，但是5号拿的一定比4号的多，因为4号的选择是X-3，而5号的选择是X-1和X-2。所以，4号的一定是最小的。所以4号的存活几率也为0。
最后看5号，5号不用说了，必死的，所以，存活几率是0。
综上所述，1号存活几率为0，2号为50%，3号为50%，4号为0，5号为0。
二、悲惨的人性。
以上分析，1号拥有首先选择的权利，可是如果1号拿20，那么1号必死。可事实是，无论1号拿几，后面的几个人都会依次递减。所以1号无论怎样存活几率都是0。因为，2号总是比他小，而5号又要尽可能多的拉人一起死，所以5号不可能选一个比1号还大的数字，如果5号真的选了比1号还大的数字，那么5号只能拉1个人死，如果5号选和1号一样的数字，会拉2个人死，可是当5号选X-1和X-2的时候，会拉3个人一起死。因此，由于2号和5号的存在，1号的所拿的数字变成了最大。所以1号无论怎样，存活几率都是0。在这种情况下，1号还会傻傻的去随便选一个数字吗？错！1号不会这么做，因为他们都是足够聪明的人，1号会想，如果我随便的选一个普通的数字，那么都会有且至少有一个人存活，这并不是1号愿意看到的，因此1号干脆会选一个非常非常特殊的数字，那就是96颗，题目规定，每人至少要拿1颗，那么，轮到2号的时候，2号一摸，还剩4颗，如果自己拿2颗，那么，还剩2颗，可是后面还有3个人，题目要求每人至少拿1颗，如果自己拿了2颗，后面3个人不够拿了，所以，最后的2号3号4号5号，都只能被迫的选择拿1颗，那么最后的结果是1号96颗，2号1颗，3号1颗，4号1颗，5号1颗。这样，由于前面的分析，如果1号随便拿一个数字，那么自己都必死，所以，自己横竖都是死，不如把所有的人全部拉进来一起死。
所以，最后1号真正的决定，只会拿96颗，让大家一起死。
三，全剧终。
如果一定要让我给这个题目做个答案，我会这么说，如果1号没有聪明到我这个程度的话，那么2号和3号的存活几率最大，分别都是50%。如果1号和我一样聪明，那么大家都死。
是否可以解决您的问题？

追问

我的问题是曼哈顿有多少路灯。

Answer 2

这个问题可以先从曼哈顿岛有序排列的街灯开始计算，然后再推及水平和垂直的方向，之后得出每个行政区的街灯数量。