Câu hỏi 15
Hãy xem xét bất kỳ bảng hình chữ nhật nào có hữu hạn nhiều hàng và cột, với số thực $a(r, c)$ trong ô ở hàng $r$ và cột $c$. Một cặp $(R, C)$, trong đó $R$ là tập hợp các hàng và $C$ là tập hợp cột, được gọi là cặp yên ngựa nếu hai điều kiện sau được thỏa mãn:
(i) Với mỗi hàng $r^{\prime}$, có $r \in R$ sao cho $a(r, c) \geqslant a\left(r^{\prime}, c\right)$ với mọi $c \in C$;
(ii) Với mỗi cột $c^{\prime}$, có $c \in C$ sao cho $a(r, c) \leqslant a\left(r, c^{\prime}\right)$ cho tất cả $r \in R$.
Một cặp yên ngựa $(R, C)$ được gọi là cặp cực tiểu nếu với mỗi cặp yên ngựa ( $R^{\prime}, C^{\prime}$ ) với $R^{\prime} \subseteq R$ và $C^{\prime} \subseteq C$, ta có $R^{\prime}=R$ và $C^{\prime}=C$.
Chứng minh rằng hai cặp cực tiểu bất kỳ đều chứa cùng số hàng.
(i) Với mỗi hàng $r^{\prime}$, có $r \in R$ sao cho $a(r, c) \geqslant a\left(r^{\prime}, c\right)$ với mọi $c \in C$;
(ii) Với mỗi cột $c^{\prime}$, có $c \in C$ sao cho $a(r, c) \leqslant a\left(r, c^{\prime}\right)$ cho tất cả $r \in R$.
Một cặp yên ngựa $(R, C)$ được gọi là cặp cực tiểu nếu với mỗi cặp yên ngựa ( $R^{\prime}, C^{\prime}$ ) với $R^{\prime} \subseteq R$ và $C^{\prime} \subseteq C$, ta có $R^{\prime}=R$ và $C^{\prime}=C$.
Chứng minh rằng hai cặp cực tiểu bất kỳ đều chứa cùng số hàng.