25 马问题

这是以前在 TopLanguage 讨论组讨论过的一道题目 ，题目描述为：

有 25 匹马和 1 个赛场，但赛场只有 5 条赛道，即一次只能给最多 5 匹马提供比赛机会，并且不能计时。请问如何设计比赛策略得到最快的 3/5 匹马，使得使用赛道的次数最少。

我想了一下，下面尝试给出我的分析，如果不对的话，还请指正。

一、决出前三名的策略

决出前 3 名网上有很多讨论，答案是 7 次，没有见过更少的，策略如下：

1. 将 25 匹马分成 5 组，分别赛一轮，得出一个先后顺序，共 5 轮。
2. 将每组的头马组成一组，再赛一轮，得出一个先后顺序。这第 6 轮能确定第一名。
3. 将最快一组的二三名，第二那组的一二名，以及第三那组的第一名五匹马放在一起，再赛一轮。这第 7 轮的前两名就是最终的二三名。总共赛 7 轮。

下面是分析。不失一般性，在赛 6 次之后，我们假设这 25 匹马的序号为：

A1 A2 A3 A4 A5  // 1 <-------
B1 B2 B3 B4 B5  // 2  |     |
C1 C2 C3 C4 C5  // 3 Main   |
D1 D2 D3 D4 D5  // 4  |  Extended
E1 E2 E3 E4 E5  // 5 <--    |
--------------  //          |
A1 B1 C1 D1 E1  // 6  {A1} <-

其中主矩阵列出了 25 匹马的序号，扩展矩阵的每行是每轮比赛的结果。我们可以看到主矩阵的行有序，第一列有序，那么现在我们知道第一名是 A1。

由于已知 A1 是第一名，第二名肯定是在每轮中紧挨在 A1 后面的，因此第二名的候选集为 {A2, B1}。

它们两个占不满 5 个赛道，我们再来看第三名的候选集。第三名在每轮中只可能是挨在第一或第二名的后面，也就是说在 {A1} U {A2, B1} 的后面，那么第三名的候选集就是 {A2, A3, B1, B2, C1}，正好 5 匹马（第二名的候选集肯定包含在第三名候选集中）。那么第二三名只可能在这 5 匹马中，因此我们只需要让 {A2, A3, B1, B2, C1} 这 5 匹马再比一次，得到前两名，与 {A1} 合起来就是总的前三名。这样总共的比赛次数是 7 次。

2. 决出前五名的策略

决出前 5 名，就比较复杂了，我们按照同样策略再往下思考：

{A2, A3, B1, B2, C1} 决出前两名，有几种可能呢？如果它们没有比过，可能性就是从 5 个中取 2 个后的排列数，20 种可能。但是我们前面的比赛已经得到了一些快慢信息，我们就可以发现，第 7 轮 {A2, A3, B1, B2, C1} 决出前两名只有 5 种可能情况：

A2 A3 B1       B2/C1 * // 7  {A1, A2, A3}
B1 B2 A3/C1    *     * // 7  {A1, B1, B2}
B1 C1 A2/B2    *     * // 7  {A1, B1, C1}
A2 B1 A3/B2/C1 *     * // 7  {A1, A2, B1}
B1 A2 A3/B2/C1 *     *

去掉可交换的 A2 B1，其实只有 4 种情况。我们分别来考虑这 4 种情况：

1. {A1, A2, A3}

第四名肯定是 {A1, A2, A3} 之后的马，候选集为 {A4, B1}；元素不足 5，再推一下第五名，即{A1, A2, A3} U {A4, B1} 之后的马，候选集为 {A4, B1, A5, B2, C1}，只有 5 匹马。就是说第四、五名可以从这五匹马中产生，那么我们只需要再比一轮，取前两名，与 {A1, A2, A3} 并起来就能得到整个的前 5 匹马。那么最少的比赛次数是 8 次。

2. {A1, B1, B2}

这种情况下，同理，第四名候选集为 {A2, B3, C1} ，第五名候选集为 {A2, A3, B3, B4, C1, C2, D1}，元素多于 5 个。因此我们必须先让 {A2, B3, C1} 比赛得到第 4 名，才能将第五名候选集的元素个数减少到 5 个以内。穷举：第 8 轮 A2 第一，可以消去 {C2, D1, B4, A2}；B3 第一，可以消去 {B3, A3, C2, D1}；C1 第一，可以消去 {C1, A3, B4}，均能保证第五名的取值集合减少到 5 以内，因此只需要再一轮，就可以得到第五名。总的比赛次数是 9 次。

3. {A1, B1, C1}

同理，第四名候选集为 {A2, B2, C2, D1}，第五名候选集为{A2, A3, B2, B3, C2, C3, D1, E1}。第四名无论取哪个，都会消去四个第五名候选集中的元素，总的比赛次数仍然是 9 次。

4. {A1, A2, B1}

同理，第四名候选集为{A3, B2, C1}，第五名候选集为{A3, A4, B2, B3, C1, C2, D1}。第四名无论取哪个，至少消去第五名候选集中的 3 个元素，总的比赛次数也是 9 次。

穷举结束了，现在我们可以得出结论：最坏情况下该策略决出前 5 匹马的最少比赛次数是 9 次。

三、扩展问题

我有一个问题是：这种策略下取3, 5名比赛次数一定是最少的吗？有没有数学证明？

再扩展一点儿，如果需要求前 n 名，最少需要比赛几次？

在我们的这种策略下，因为主矩阵只有 5 行，每行还是有序的，那么求下一名的候选集最多有 5 个元素。也就是说多求一名，至多需要增加一轮比赛。什么情况下可以少于一轮呢？当已经确定第 n 名的情况时，第 n+2 名的候选集元素少于 5 个，我们就可以一轮比赛确定两个名次了。

我还比较好奇的是，如果需要决出所有 25 匹马的快慢顺序，最坏情况下至少需要比赛几次？

在我们这种策略下，假设 f(n) 是第 n 名最坏情况下的最少比赛次数，我们已知 f(1) = 6, f(2) = f (3) = 7, f(4) = 8, f(5) = 9，f(n) <= (n-5)+9 = n+4。那么 f(25) = f(20)+1 <= (20-5)+9 + 1 = 25 次，其上界应该是 25。但其准确值怎么确定？穷举就太困难了。 但是如果题目要求是确定 25 个的全部顺序，我们这种策略未必是最好的。这时候这题可以看成 n 路归并排序，并且可同时比较 n 个数的优化问题。过程中有很多可优化的可能。比如我们预处理时可以对每行和每列都排一下序，能否可以得到一些额外的信息？当主矩阵（去掉已确定顺序的元素）显得不那么平衡时，用扩展矩阵中的比较信息是否可以将主矩阵平衡一下，或者消去某些行列，这样做是否有帮助？