經典邏輯題：10×10 方陣「行最大值的最小值」vs「列最小值的最大值」誰大？

問題描述

100 人排成 10×10 方陣。
甲：每行挑最高 → 10 人 → 再挑最矮。
乙：每列挑最矮 → 10 人 → 再挑最高。
問：甲、乙誰高？

數學建模

• 原始矩陣：person[i][j] (i=行, j=列)
• 每行最大值：rowMax[i] = max_j(person[i][j])
• 每列最小值：colMin[j] = min_i(person[i][j])
• 甲 = min_i(rowMax[i]) —— 行最大值中的最小值
• 乙 = max_j(colMin[j]) —— 列最小值中的最大值

核心證明：甲 ≥ 乙 恆成立

性質

• 甲 ≥ 同行任意元素（因為甲是該行最大值中的最小值，但甲所在行的最大值 ≥ 甲）
• 乙 ≤ 同列任意元素（因為乙是該列最小值中的最大值，但乙所在列的最小值 ≤ 乙）

三種情況窮盡

1. 同行或同列：直接比較，甲 ≥ 乙。
2. 同一人：甲 = 乙。
3. 不同行不同列：設甲位於 (r, c₁)，乙位於 (r₁, c)。交點 (r, c) 滿足：

   甲 ≥ person[r][c] （甲 ≥ 同行所有元素）
   乙 ≤ person[r][c] （乙 ≤ 同列所有元素）
   ∴ 甲 ≥ person[r][c] ≥ 乙  →  甲 ≥ 乙
       

結論：甲 ≥ 乙 恆成立，等號僅在特定矩陣（如遞減矩陣）時成立。

等號成立範例：5×5 遞減矩陣

9 8 7 6 5
8 7 6 5 4
7 6 5 4 3
6 5 4 3 2
5 4 3 2 1

• 行最大值：{9,8,7,6,5} → 甲 = 5
• 列最小值：{5,4,3,2,1} → 乙 = 5
• 甲 = 乙 = 5，且為同一人（右下角）。

博弈論視角：鞍點與極大極小定理

此問題對應零和博弈的極大極小值：
max_min ≤ min_max 恆成立（von Neumann 極大極小定理）。
甲 = max_min（行玩家保守策略），乙 = min_max（列玩家保守策略）。
若存在鞍點，則甲 = 乙 = 鞍點值，雙方均無單方面改變策略的誘因。

程式碼驗證

int[][] a = {{9,8,7,6,5},{8,7,6,5,4},{7,6,5,4,3},{6,5,4,3,2},{5,4,3,2,1}};
int jia = Arrays.stream(a).mapToInt(row -> Arrays.stream(row).max().getAsInt()).min().getAsInt();
int yi  = IntStream.range(0,5).map(c -> Arrays.stream(a).mapToInt(r -> r[c]).min().getAsInt()).max().getAsInt();
System.out.println("甲=" + jia + " 乙=" + yi); // 甲=5 乙=5

總結

**甲（行極大值的極小值）永遠 ≥ 乙（列極小值的極大值）。** 這不只是邏輯題，更是博弈論、優化理論、矩陣分析的基石結論。下次面試遇到類似「極大極小」「鞍點」關鍵字，直接推導此不等式即可。