--- description: "5 场分组 + 1 场组冠军赛 + 1 场候选赛 = 7 场；每场至多造出 4 个输家，对手论证卡死第 6 场" --- # 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 名。 ??? note "数值验证" 把已知结果存成传递闭包，对手枚举所有与之不矛盾的名次，极小极大搜索"还剩 $d$ 场能否在最坏情况下排出前 $K$ 名"。上场的马只挑候选——非候选马上场，对手把它排最后就等于没上： ```python 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 场 ``` 整段跑约两分多钟，大头在前 5 名那一行。