25 匹马找出最快的 3 匹
Horse Racing
题目详情
有 25 匹马，速度各不相同且恒定。赛道只有 5 条跑道，因此一次最多只能让 5 匹马比赛。
你没有秒表，只能观察每场比赛的名次。
问：最少需要比赛多少场，才能唯一确定最快的 3 匹马？
There are 25 horses, each of which runs at a distinct and constant speed. The track has five lanes, and thus can race at most five horses at once. By simply racing different sets of horses and observing the placing of the horses within those races without access to a stopwatch, what is the minimum number of races needed to uniquely identify the three fastest horses?
解析
先分成 5 组各 5 匹，先赛 5 场，得到每组内部排序。
再让 5 组各自的第一名再赛 1 场，确定总体第一名，并据此淘汰不可能进入前三的马。
最后只需在候选集（通常为 5 匹）中再赛 1 场即可确定第 2、3 名。
总计最少需要 场。
Original Explanation
To find the three fastest horses, all horses need to be tested. A natural first step will then be to divide the horses into five groups labeled 1-5, 6-10, 11-15, 16-20, and 21-25. After these five races, we have the order of the horses within each group. Without loss of generality, assume the order within each group follows the order of the numbers (e.g., 6 is the fastest and 10 is the slowest within the 6-10 group). Therefore, the five fastest horses are 1, 6, 11, 16, and 21. We can eliminate the last two horses from each group since they cannot possibly be within the top three. We will then race the top five horses to establish the fastest horse. Again, assume the order of this group follows the order of the numbers (e.g., 1 is the fastest and 21 is the slowest). This tells us that from the first group 1-5, only 2 and 3 are in the running for second and third; from the second group 6-10, only 6 and 7 are in the running for second and third; and from the third group 11-15, only 11 is in the running for second or third. This is because if the fastest horse within a group ranks second or third, then only one or no other horses within that group can be in the top three, respectively. Hence, the last group will race 2, 3, 6, 7, and 11, for a total of 7 races.