这是个非常经典的贪心最优性证明问题，我们可以用交换论证法（Exchange Argument）来严谨证明这个策略的最优性——这是贪心算法证明的核心方法之一，思路很直观：假设存在一个比贪心解更好的最优解，我们通过逐步调整这个最优解，让它和贪心解的结构一致，同时保证错误数不会增加，最终证明贪心解至少和最优解一样好。

先明确几个定义 #

• 对于每个玩家 (i)，记 loss(i) 为 (i) 输掉的对战次数（只统计实际发生过的对战）。
• 贪心解 (W_g)：选取败场最少的 (n/2) 名玩家；对应的败者组 (L_g) 是剩下的 (n/2) 名玩家。
• 假设存在一个最优解 (W_{opt})、(L_{opt})，其错误数 (E_{opt} \leq E_g)（(E_g) 是贪心解的错误数）。我们的目标是证明 (E_{opt} = E_g)，且可以将 (W_{opt}) 调整为 (W_g) 而不增加错误数。

核心交换论证步骤 #

1. 找到可交换的玩家对
   因为 (W_g) 和 (W_{opt}) 大小相同，必然存在这样一对玩家：

   • (u \in W_{opt}) 但 (u \notin W_g)（即 loss(u) 比 (W_g) 中至少一个玩家的败场数多）；
   • (v \in L_{opt}) 但 (v \in W_g)（即 loss(v) ≤ loss(u)）。

2. 交换后的错误数分析
   我们将 (u) 从 (W_{opt}) 移到 (L_{opt})，(v) 从 (L_{opt}) 移到 (W_{opt})，得到新解 (W' = W_{opt} \setminus {u} \cup {v})、(L' = L_{opt} \setminus {v} \cup {u})。现在需要证明：交换后的错误数 (E' \leq E_{opt})。

   错误数的变化来自三部分：

   • (u) 和 (v) 之间的对战：

     • 原状态：(u \in W_{opt})、(v \in L_{opt})。如果 (u) 输给 (v)，这算1个错误；如果 (u) 赢了 (v)，不算错误。
     • 新状态：(v \in W')、(u \in L')。如果 (v) 输给 (u)，这算1个错误；如果 (v) 赢了 (u)，不算错误。
     • 这部分的变化：若 (u) 输给 (v)，交换后错误数减少1；若 (u) 赢了 (v)，交换后错误数增加1；若未对战，无变化。

   • (u) 与其他玩家的对战：

     • 原状态：(u) 在 (W_{opt})，所有 (u) 输给 (L_{opt}) 中玩家的对战都算错误；交换后 (u) 在 (L')，这些对战不再算错误，错误数减少 (A)（(A) 是 (u) 输给 (L_{opt}) 中玩家的次数）。
     • 同时，原状态中 (W_{opt}) 其他玩家输给 (u) 的对战不算错误；交换后这些对战变成 (W') 玩家输给 (L') 玩家，算错误，错误数增加 (B)（(B) 是 (W_{opt}) 其他玩家输给 (u) 的次数）。

   • (v) 与其他玩家的对战：

     • 原状态：(v) 在 (L_{opt})，所有 (v) 输给 (L_{opt}) 中玩家的对战不算错误；交换后 (v) 在 (W')，这些对战算错误，错误数增加 (D)（(D) 是 (v) 输给 (L_{opt}) 中玩家的次数）。
     • 同时，原状态中 (W_{opt}) 其他玩家输给 (v) 的对战不算错误；交换后这些对战仍在 (W') 内部，不算错误，无变化。

3. 利用败场数的关系推导
   因为 loss(v) ≤ loss(u)，而：

   • loss(v) = (v) 输给 (W_{opt}) 玩家的次数 + (D) +（1如果 (v) 输给 (u)，否则0）
   • loss(u) = (u) 输给 (W_{opt}) 玩家的次数 + (A) +（1如果 (u) 输给 (v)，否则0）

   结合 loss(v) ≤ loss(u)，可以推导出：交换后错误数的总变化 (\Delta E = E' - E_{opt} \leq 0)。也就是说，交换后的错误数不会超过原来的最优解。

结论 #

如果最优解中存在不符合贪心策略的玩家对（即败场多的在胜者组，败场少的在败者组），我们可以通过交换这些玩家对，得到一个错误数不增加的新解。重复这个过程，最终最优解会被调整为贪心解，且错误数不变或减少。这就证明了：按败场数排序选取败场最少的 (n/2) 名玩家作为胜者组的贪心策略，是最小化错误数的最优解法。

内容的提问来源于stack exchange，提问作者Ayumu Kasugano