A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「Wise Man」.

Wise Man #

Problem #

A sultan has captured $50$ wise men. He has a glass currently standing bottom down. Every minute he calls one of the wise men who can choose either to turn it over (set it upside down or bottom down) or to do nothing. The wise men will be called randomly, possibly for an infinite number of times. When someone called to the sultan correctly states that all wise men have already been called to the sultan at least once, everyone goes free. But if his statement is wrong, the sultan puts everyone to death. The wise men are allowed to communicate only once before they get imprisoned into separate rooms (one per room). Design a strategy that lets the wise men go free.

Solution 1 #

寻找一个话事人, 他每次进入房间, 如果看到杯子是底朝上, 就将其翻转, 否则什么也不做. 对于另外的 $49$ 个人, 他们进入房间时, 如果不曾翻转过杯子且看到杯子底朝下, 就将其翻转; 否则什么也不做. 这种策略实际上让话事人充当了一个计数器, 当他第 $49$ 次将底朝上的杯子翻转过来时, 他就知道所有人都已经进入过房间了.