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

Horse Race #

Problem #

There are 25 horses, cach of which runs at a constant speed that is different from the other horses’. Since the track only has 5 lanes, each race can have at most 5 horses. If you need to find the 3 fastest horses, what is the minimum number of races needed to identify them?

Solution #

首先, 每 $5$ 匹马分成一组, 进行比赛. 将五个组的小组第一 (不妨设为 $1,6,11,16,21$) 再进行一次比赛 (设结果是 $1>6>11>16>21$), 排第四、第五的马所在小组不可能有马在前三; 排第三的马所在的小组只有它自身 ($11$) 可能进前三; 排第二的马所在的小组的第一第二 ($6, 7$) 都可能进前三; 排第一的马是所有马的第一名, 同时它所在的小组第二第三 ($2, 3$) 可能进前三. 让 $2, 3, 6,7,11$ 再进行一次比赛可以知道所有马的第二第三. 综上, 想要找到最快的三匹马, 需要 $5+1+1=7$ 轮比赛.