题目
赛马问题(25 匹马,每匹马的速度都不一样,一次竞赛只能跑 5 匹马,问最少需要多少次竞赛才能找出最快的 3 匹马)
答案
要找出 25 匹速度各不相同的马中最快的 3 匹,且每次只能比 5 匹马,最少需要 **7** 次比赛。方案如下:
1. **分组预赛(5 场)**:将 25 匹马分成 5 组(A、B、C、D、E),每组 5 匹马,各组内部进行一场比赛,共进行 5 场。
- 比赛结果记录为:
- 组 A 排名:A₁ > A₂ > A₃ > A₄ > A₅
- 组 B 排名:B₁ > B₂ > B₃ > B₄ > B₅
- 以此类推……
2. **各组冠军赛(1 场,第 6 场)**:让每组的冠军(A₁, B₁, C₁, D₁, E₁)再赛一次,按名次进行排序,假设结果为:
```
A₁ > B₁ > C₁ > D₁ > E₁
```
那么我们可以确定:
- A₁ 是全场最快。
- A 组整体速度最快,其次是 B 组,再次是 C 组……
3. **决出第 2、3 名的候选者筛选**:由于只有 A、B、C 组三匹马中可能出现全场第 2、3 名,其它组的马都不可能比 C₁(冠)慢的 C₂、C₃ 更快:
- A 组:A₂、A₃(A₁ 已确认为第 1)
- B 组:B₁(已在冠军赛中为第 2)、B₂
- C 组:C₁
一共 5 匹马:A₂、A₃、B₁、B₂、C₁。
4. **决赛(1 场,第 7 场)**:把上述 5 匹马再赛一次,名次第 1、第 2 即为全场第 2、第 3。
