25 匹马找前 3 名

题

25 匹马，一个赛场 5 条赛道，每场最多 5 匹马同跑。没有计时器，每场只能看到这几匹马的先后名次。马的速度恒定（重跑结果不变）且两两不同。最少跑几场，能保证找出最快的 3 匹并排好名次？

一句话

7 场。 5 场分组赛，5 个组冠军再跑 1 场；这时还有资格争第 2、3 名的只剩 5 匹马，正好一场跑完。

关键技巧

两件工具。

一、候选集按"已知比它快的马"来筛。 一匹马只要已知有 3 匹马比它快，就出局。分组赛后按组冠军的名次给组排序（A 组冠军最快，E 组最慢），记 \(X_i\) 为 \(X\) 组第 \(i\) 名。\(X_i\) 前面至少压着本组的 \(i-1\) 匹，外加名次比 \(X\) 靠前的组冠军——它们都比 \(X_1\) 快，从而比 \(X_i\) 快。所以已知比 \(C_2\) 快的至少有 \(C_1, B_1, A_1\) 三匹，出局；\(B_3\) 前面有 \(B_2, B_1, A_1\)，出局。

二、下界靠对手论证（adversary argument）。 把比赛结果想象成由一个刁难你的对手临场决定，他唯一的约束是不能和已经跑出的结果矛盾。你的方案要在对手最坏的安排下仍然成功。

解

1. 第 1–5 场：分 5 组各跑一场，得到组内名次。
2. 第 6 场：5 个组冠军同跑。第一名 \(A_1\) 就是总冠军。

3. 筛候选：第 2、3 名只可能在下表打勾的 5 匹里：

   	第 1 名	第 2 名	第 3 名	第 4、5 名
   A 组	总冠军	✓	✓	前有 3 匹
   B 组	✓	✓	前有 \(B_2, B_1, A_1\)	出局
   C 组	✓	前有 \(C_1, B_1, A_1\)	出局	出局
   D、E 组	前有 \(C_1, B_1, A_1\)	出局	出局	出局

4. 第 7 场：\(A_2, A_3, B_1, B_2, C_1\) 同跑，前两名就是总第 2、3 名。

为什么 6 场不够

连冠军都要 6 场。 确定冠军，意味着其余 24 匹每匹都至少输过一次——没输过的马都可能是冠军。一场 5 匹马至多产生 4 个"第一次输"的马，\(24 / 4 = 6\)。

6 场恰好够冠军，前提是每场的 4 个输家都是第一次输。 对手的策略：只要某场里有已经输过的马，就让一匹没输过的马赢——没输过的马头上没有已知更快的马，放第一永远不矛盾——于是那匹输过的马又输一次，这场的"首次输家"不足 4 个，6 场凑不齐 24 个。所以 6 场的方案里，每场上场的 5 匹都必须从未输过，整个赛程是一棵淘汰赛树。

这棵树上第 2 名必然悬空。 5 场之后恰好剩 \(25 - 20 = 5\) 匹没输过的马，它们全部要进第 6 场，其中必有第 5 场的胜者 \(W\)。对手让 \(W\) 在第 6 场也赢。现在 \(W\) 是冠军，第 5 场的第二名 \(P\) 和第 6 场的第二名 \(Q\) 都只输给过 \(W\)——\(P\) 输过一次就再没资格上场，\(Q\) 到第 6 场前从没输过，两匹马从未交手——第 2 名是谁，6 场结束也说不出来。所以前 2 名就要 7 场，前 3 名当然也是。

延伸

• 只找第 1 名：6 场，下界就是上面第一步。
• 前 2 名：也是 7 场。6 场后第 2 名的候选只有 \(A_2, B_1\)，第 7 场只用两条赛道。
• 候选集是个阶梯：找前 \(K\) 名时，\(X_i\)（\(X\) 为第 \(j\) 个组）留在候选里的条件是 \(i + j \le K + 1\)，除去总冠军共 \(\frac{K(K+1)}{2} - 1\) 匹。\(K = 3\) 是 5 匹，\(K = 4\) 是 9 匹，\(K = 5\) 是 14 匹。
• 前 4 名要 8 场，前 5 名要 9 场：在"5 场分组 + 1 场冠军赛"这个开局之后，让对手穷举所有不矛盾的结果做最坏打算（折叠块里的搜索），前 4 名还需 2 场，前 5 名还需 3 场——14 匹候选争 4 个位置，两场只有 10 条赛道。换一种开局能不能更省，本文没有证。
• 64 匹马 8 条赛道找前 4 名：11 场。8 场分组 + 1 场冠军赛后，候选是 \(A_2, A_3, A_4, B_1, B_2, B_3, C_1, C_2, D_1\) 共 9 匹，比赛道多 1 匹。不管第 10 场漏掉谁，对手都能让漏掉的那匹成为悬念——一场不够，两场够。常见错误答案是 10。
• 常见错误：第 7 场把 \(A_1\) 也拉上，白占一条赛道；或者漏掉 \(B_2\)——它前面只有 \(B_1\) 和 \(A_1\)，完全可能是第 3 名。

from itertools import combinations, permutations

def race(below, order):
    """记一场比赛（order 从快到慢），更新传递闭包。below[h] = 已知比 h 慢的马集合（位掩码）。"""
    b = below[:]
    for x, y in zip(order, order[1:]):
        add = b[y] | 1 << y
        for h in range(len(b)):
            if h == x or b[h] >> x & 1:
                b[h] |= add
    return b

def cands(b, K):
    """已知比它快的马不足 K 匹 = 还可能进前 K。"""
    above = [sum(b[g] >> h & 1 for g in range(len(b))) for h in range(len(b))]
    return [h for h in range(len(b)) if above[h] < K]

def solved(b, K):
    u = cands(b, K)
    return len(u) == K and all(b[x] >> y & 1 or b[y] >> x & 1 for x, y in combinations(u, 2))

def outcomes(b, S):
    """与已知结果不矛盾的全部名次。"""
    for p in permutations(S):
        if not any(b[p[j]] >> p[i] & 1 for i in range(len(p)) for j in range(i + 1, len(p))):
            yield p

def can(b, K, L, d):
    """还剩 d 场、每场 L 条赛道，能否在最坏情况下排出前 K 名。只让候选马上场不失一般性。"""
    if solved(b, K): return True
    if d == 0: return False
    u = cands(b, K)
    return any(all(can(race(b, p), K, L, d - 1) for p in outcomes(b, S))
               for S in combinations(u, min(L, len(u))))

def opening(G, L):
    """G 组各跑一场 + 各组第一再跑一场。马 g*L+i = 第 g 组第 i 名，组按组冠军名次排。"""
    b = [0] * (G * L)
    for g in range(G):
        b = race(b, [g * L + i for i in range(L)])
    return race(b, [g * L for g in range(G)])

b = opening(5, 5)
print(len(cands(b, 3)) - 1, can(b, 3, 5, 1))        # 5 True    第 7 场收官
print(can(b, 4, 5, 1), can(b, 4, 5, 2))             # False True  前 4 名：8 场
print(can(b, 5, 5, 2), can(b, 5, 5, 3))             # False True  前 5 名：9 场
b = opening(8, 8)
print(len(cands(b, 4)) - 1, can(b, 4, 8, 1), can(b, 4, 8, 2))   # 9 False True  64 马：11 场