Birthday Problem
Table of Contents
A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「Birthday Problem」.
Birthday Problem #
Problem #
You and your colleagues know that your boss A’s birthday is one of the following 10 dates:
- Mar 4, Mar 5, Mar 8
- Jun 4, Jun 7
- Sep 1, Sep 5
- Dec 1, Dec 2, Dec 8
A told you only the month of his birthday, and told your colleague C only the day. After that, you first said: “I don’t know A’s birthday; C doesn’t know it either.” After hearing what you said, C replied: “I didn’t know A’s birthday, but now I know it.” You smiled and said: “Now I know it, too.” After looking at the 10 dates and hearing your comments, your administrative assistant wrote down A’s birthday without asking any questions. So what did the assistant write?
Solution #
不妨列一个表格:
| 1 | 2 | 4 | 5 | 7 | 8 | |
|---|---|---|---|---|---|---|
| Mar | 0 | 0 | 1 | 1 | 0 | 1 |
| Jun | 0 | 0 | 1 | 0 | 1 | 0 |
| Sep | 1 | 0 | 0 | 1 | 0 | 0 |
| Dec | 1 | 1 | 0 | 0 | 0 | 1 |
把整个过程分成三个阶段. 记原文中 “You” 为 B.
- B 自己仅凭月份不能确定生日(这句话在本题中没有信息量) , 但 B 断定 C 同样不能确定, 这直接排除了 Jun (Jun 7) 和 Dec (Dec 2) .
- 在排除 Jun 和 Dec 后, C 确定了生日, 因此排除了 Mar 5 和 Sep 5 .
- 得到这个信息后, B 确定了生日, 说明 B 知道的月份是 Sep .
最终助手写下的生日是 Sep 1.