Câu hỏi 8
Cho $m,n$ là các số nguyên dương. Mỗi ô $(r,c)$ trong một bảng $m\times n$ chứa một số thực $a(r,c)$. Chọn tập hàng $R\subseteq\{1,2,\ldots,m\}$ và tập cột $C\subseteq\{1,2,\ldots,n\}$. Gọi $(R,C)$ là một cặp tốt nếu cả hai điều kiện sau đều đúng:
- Điều kiện 1. Với mọi $r'\in\{1,2,\ldots,m\}$, tồn tại $r\in R$ sao cho $a(r,c)\ge a(r',c)$ với mọi $c\in C$.
- Điều kiện 2. Với mọi $c'\in\{1,2,\ldots,n\}$, tồn tại $c\in C$ sao cho $a(r,c)\le a(r,c')$ với mọi $r\in R$.
Một cặp tốt $(R,C)$ được gọi là cực tiểu nếu mọi cặp tốt $(R',C')$ thỏa $R'\subseteq R$ và $C'\subseteq C$ đều có $R'=R$ và $C'=C$. Chứng minh tập hàng của hai cặp cực tiểu bất kỳ có cùng số phần tử.
- Điều kiện 1. Với mọi $r'\in\{1,2,\ldots,m\}$, tồn tại $r\in R$ sao cho $a(r,c)\ge a(r',c)$ với mọi $c\in C$.
- Điều kiện 2. Với mọi $c'\in\{1,2,\ldots,n\}$, tồn tại $c\in C$ sao cho $a(r,c)\le a(r,c')$ với mọi $r\in R$.
Một cặp tốt $(R,C)$ được gọi là cực tiểu nếu mọi cặp tốt $(R',C')$ thỏa $R'\subseteq R$ và $C'\subseteq C$ đều có $R'=R$ và $C'=C$. Chứng minh tập hàng của hai cặp cực tiểu bất kỳ có cùng số phần tử.