绿皮书里的智力面试题

作者: , 共 2918 字
系列:头脑风暴

查看该系列所有文章

题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。

1. 题目

1. A 让 C 要送一份资料给 B。但 C 不可靠, A 可以把资料放在盒子里锁上才能送给 B ,但 B 也需要拿到钥匙才能打开盒子。问 A 有方法将资料安全送达 B 处吗?

2. 房间里有一盏灯。房间外有四个开关,但只有一个开关是控制灯泡。现在四个开关都处于关闭状态。问能否只进入房间一次,就能找出控制灯泡的开关。

3. 在一个黑房间里有 100 枚硬币,其中 20 枚正面朝上,其它的反面朝上。你看不到各枚硬币的朝向,也不允许以任何形式来分辨它,但允许你对它们进行翻转(在不知朝向的情况下)。问你是否可能将这些硬币分成两堆,这两堆硬币有相同多的正面朝上的硬币。

4. 三袋水果,其中一袋里面是苹果,第二袋是桔子,第三袋既有苹果也有桔子。在袋子外面有标签标明袋子的内容。但不幸的是,你被告知三个袋子的标签都被标错了。你现在可以从袋子里拿出水果来分辨袋子。问:你至少需要拿出几个水果,才能更正这三个袋子的标签?

5.  监狱里关了 50 个囚犯。监狱长有一个硬币,现在正面朝上。每分钟监狱长会叫入一个囚犯。这个囚犯可选择翻转硬币或者不翻转。如果有囚犯宣布每个囚犯都被叫入至少一次,并且情况确实如此,那么所有囚犯都会被释放;如果出现错误,那么所有囚犯都会被处死。囚犯在关入单人监狱之前可以商议策略,但之后不能有任何交流。问囚犯能达成策略吗?

6. 1 只钟从墙上摔下来,裂成三个完整的碎片。我们发现三碎片上数字之和相同。问各碎片上的数字。

7. 手头有 98 个不同的整数,取值范围为 1 到 100。问如何快速找到两个缺失的数。

8. 10 个袋子里分别有 100 枚硬币。其中 9 个袋子里的硬币是一样重的,每个硬币都是 10 克。另外一个袋子里硬币也都是一样,但重量都是 9 克或者都是 11 克。问怎么只用一次带刻度的电子秤分辨出与众不同的袋子以及具体的重量。

9. 五个袋子里分别有 100 枚硬币。每个袋子里的硬币都是一样的,但不同袋子的硬币可能不一样,可能有三种重量,分别为 9 克、10 克和 11 克。问至少需要使用几次带刻度的电子秤才能分辨出每个袋子的硬币重量?

10. 一个与世隔绝的岛屿上有 13 个黑人、15 个白人和 17 个黄种人。任何两种不同皮肤的人遇到一起,就会都变成另外一种颜色。问是否可能所有人都变成同一种颜色?

11. 你有 100 个硬币。首先你将它分成两堆,分别有 x 枚和 y 枚硬币,得到它们的乘积。再任意将其中的一堆分成两堆,得到两个小堆的硬币数量的乘积。这样一直分下去直到每个堆只有一枚硬币无法再分为止。将所有得到的乘积加起来,问最后这样的乘积和最大是多少?

12. 一个 6×8 的棋盘,你需要逐步将其分拆成小方块。你每次可以选择其中的一块,沿着方块边界将它分成两部分,比如你开始将 6×8 的棋盘分成一个 6×3 和一个 6×5 的小棋盘。问你至少需要分多少次,才能将棋盘分成 48 块小方格。

13. 一个单向的环形跑道上有 100 个随机分布的加油站,每个加油站里有油,合计起来恰好够汽车跑一个整圈。你有一辆汽车,刚开始时汽车油箱是空的,但一遇到加油站就可以加油。问你是否总是可以选择合适的出发点,使得汽车能够跑完一圈?

14. 监狱里有 7 名囚犯。监狱长给这些囚犯每人都带了个帽子,共有七种颜色(分别为彩虹七色)。各个囚犯都能看到其它人的帽子颜色,但看不到自己头上的帽子。之后监狱长让囚犯猜测自己头上的帽子颜色。只要有一人猜对,所有囚犯都会被释放。如果所有人都猜错了,所有囚犯都会被处死。囚犯不能听到其它人的猜测且不能互相交流。问囚犯可以使用什么策略,最大化被释放的概率?

2. 答案

1. A 将盒子加锁寄给 B , B 再加一把锁送还给 A , A 将自己的锁取下后再送给 B。

2. 假设开关编号为 1、2、3、4。那么首先打开 1 和 2 ,开 1 分钟;然后关掉 2 ,打开开关 3。迅速进入房间,摸一摸灯泡的热度。如果灯泡是热的,并且灯是亮的,那么答案是 1 ;如果灯泡是热的,灯是熄的,那么答案是 2 ;如果灯泡是冷的,并且灯亮着,那么答案是 3 ;否则答案是 4。

3. 先随便将硬币分为两堆,其中一堆是 20 枚,另一堆为 80 枚。然后翻转第一堆所有硬币。

4. 根据已知条件,三个袋子的标签都被标错了,那么正确标签只有两种可能性。只需要从目前标记为混合水果的口袋拿出一个水果,根据这个水果的种类就能区分这两种可能性。

5. 这个题目有一个隐含的假设,即每个人都无限次甚至随机地被叫入。在这种情况下,任选一人作为观察者,当碰到硬币正面朝下时则翻转硬币,否则什么都不做。其余每个囚犯在被叫入时如果硬币正面朝上则翻转硬币,,而且这 49 个囚犯只在第一次碰到这种情况时进行操作,其它情况什么都不做。这样当观察者翻了 49 次硬币之后,他可以确定其余 49 个囚犯都被叫入过。

6. 关键是注意 1 和 12 是连续的,剩下就简单了。

7. 计算 98 个数的和与 1 到 100 的和的差,即为缺失的两个数的和;计算 98 个数的平方和与 1 到 100 的平方和的差,即为缺失的两个数的平方和;剩下来的工作是解一个两元方程。

8. 从第 i 个袋子里取出 i 枚硬币,放在一起秤。其重量与 450 的差即使与众不同的袋子的编号,重量大于 0 表示该袋子里的硬币重 11 克,否则重 9 克。

9. 从第 i 个袋子里取出 3^(i-1)枚硬币,一起秤重量。不妨设硬币的重量分别为 0 克、1 克和 2 克。接下来即秤出的重量的三进制表示问题。

10. 不能。假设有 x 个白人、y 个黑人和 z 个黄种人,那么 y+2z 被 3 除的余数是一个不变量。刚开始等于 1 ,它不可能变成 0。

11. 100×99/2 = 4950。无论怎么分,最后得到的值都是对数。即任何两个硬币,它们恰好在其中某次被分开并被统计一次。

12. 每分一次碎片数量增加 1。一开始是 1 块,最后是 48 块。故恰好需要分 47 次。

13. 假设加油站的油量分别是 y1, y2, ..., y100 ,距离下一个加油站的距离是 z1, z2, ..., z100。令 xi = yi - zi。那么题目所需要的是证明一定存在某个开始位置,使得从该位置开始的任何长度的连续 xi 序列之和都大于 0。我们先取出和最小的连续一段 xi ,那么从这一段的下一个加油站开始即可。如果该加油站不满足要求的话,从该加油站开始还有和小于 0 的连续段,这与它前面的和最小的连续段加起来可得到和更小的一段,矛盾。

14. 假设帽子颜色标号为 0 到 6。 第 n 名囚犯回答自己的帽子颜色为 n 减去他看到的其他囚犯的帽子颜色之和,然后再被 7 除的余数。假设 7 个人的帽子颜色之和被 7 除的余数为 k ,那么第 k 名囚犯一定答对了。

Q. E. D.

系列: 头脑风暴 »
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
数学 » 头脑风暴
发信人: GGGGDDDDK (忠贾诩发动乱武,反华佗没法急救别人了), 信区: SanGuoSha
标   题: 据说此题是入职腾讯游戏策划部门一道题 zz
发信站: 水木社区 (Mon Sep 20 11:10:40 2010), 站内
类似文章:
相似度: 0.169
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
相似度: 0.137
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个\( 2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
相似度: 0.135
这个题目听说是 MSRA 的面试题。
相似度: 0.081
这是一个老问题,最近有老同学问起,就在这里提一下吧。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
相似度: 0.080
\( n\) 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
相似度: 0.078
数学 » 概率, 测试
所有大学生都应该学的两门课程,一是经济学,二是概率论,这两门课分表代表着一种生活中的思维方式。来测试一下你的概率论学得怎么样吧。题目作者: wzz12346@newsmth, 原发 Mathematics@newsmth。解答亦来自 wangzz。题目顺序和答案经过调整。
相似度: 0.077
最近看到一个有趣的问题:
在 MIT BBS 上看到一个有趣的题目
一个非常好的面试题。难度适中。
碎碎念 » 地铁
以前 13 号线转 2 号线时,总在想世上没有比这更 SX 的换乘路径了吧,结果今天 2 号线转 13 号线推翻了这一点。
编程 » Matlab, swap, 函数包
Matlab 程序效率低下,其中一个原因就是它的参数无法引用,每次都是传值。这不但导致效率问题,要实现某些功能,也需要一些特殊的手段。比如最简单的,如果交换两个变量的值,也就是在 C/C++里的函数 void swap(int& a, int& b),在 C/C++里实现很容易,但在 Matlab 里,你会吗?