题目
赛马问题(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。