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

Defective Ball #

Problem #

You have 12 identical balls. One of the balls is heavier OR lighter than the rest (you don’t know which). Using just a balance that can only show you which side of the tray is heavier, how can you determine which ball is the defective one with 3 measurements?

Solution #

经典的称硬币问题, 事实上, 加强问题 (有可能不存在假币) 也是可以解决的. 我们来讨论这个加强问题. 需要用 $3$ 次称量找出有瑕疵的球, 应该考虑决策树的深度的最小值. 因此每次将称量后的可能状态尽可能均分. 用 $i+$ 代表第 $i$ 个球有瑕疵并且更重的情况, 用 $i-$ 代表第 $i$ 个球有瑕疵并且更轻的情况, 最后还有所有球都没有瑕疵的情况, 记作 A .

第一次称量, 选取 $(1, 2, 3, 4)$ 与 $(5, 6, 7, 8)$ , 可能的结果集合是:

• 左侧重: ${1+, 2+, 3+, 4+, 5-, 6-, 7-, 8-}$
• 右侧重: ${1-, 2-, 3-, 4-, 5+, 6+, 7+, 8+}$
• 一样重: ${9+, 9-, 10+, 10-, 11+, 11-, 12+, 12-, A}$

一结果为左的后续称量 #

如果第一次称量结果为左侧重, 那么第二次称量, 选取 $(1, 2, 6)$ 和 $(3, 4, 5)$ , 可能的结果集合是:

• 左侧重: ${1+, 2+, 5-}$
• 右侧重: ${3+, 4+, 6-}$
• 一样重: ${7-, 8-}$

以 ${1+, 2+, 5-}$ 为例, 将 $(1)$ 和 $(2)$ 对比, 如果左侧重, 说明 ${1+}$ ; 如果右侧重, 说明 ${2+}$ ; 如果一样重, 说明 ${5-}$ . 其它两种情况类似.

一结果为右的后续称量 #

一结果为左的对称情况, 同上

一结果为平衡的后续称量 #

如果第一次称量结果为平衡, 那么第二次称量, 选取 $(9, 10, 11)$ 与 $(1, 2, 3)$ , 注意这种情况下 $(1, 2, 3)$ 都是没有瑕疵的球. 可能的结果集合:

• 左侧重: ${9+, 10+, 11+}$
• 右侧重: ${9-, 10-, 11-}$
• 一样重: ${12+, 12-, A}$

以 ${9+, 10+, 11+}$ 为例, 将 $(9)$ 和 $(10)$ 对比, 如果左侧重, 说明 ${9+}$ ; 如果右侧重, 说明 ${10+}$ ; 如果一样重, 说明 ${11+}$ . 其它两种情况类似.