Câu hỏi 117
Xét một bảng chữ nhật hữu hạn hàng,cột, ô hàng $r$,cột $c$ chứa số thực $a(r,c)$. Cặp(R,C), với $R$ là tập hàng,$C$ là tập cột, gọi là cặp yên ngựa nếu:
(i) Với mỗi hàng $r'$, có $r\in R$ sao cho $a(r,c)\ge a(r',c)$ với mọi $c\in C$;
(ii) Với mỗi cột $c'$, có $c\in C$ sao cho $a(r,c)\le a(r,c')$ với mọi $r\in R$.
Cặp yên ngựa(R,C) gọi là tối tiểu nếu mọi cặp yên ngựa(R′,C′) với $R'\subseteq R,C'\subseteq C$ đều có $R'=R,C'=C$. Chứng minh mọi hai cặp tối tiểu có cùng số hàng.
(i) Với mỗi hàng $r'$, có $r\in R$ sao cho $a(r,c)\ge a(r',c)$ với mọi $c\in C$;
(ii) Với mỗi cột $c'$, có $c\in C$ sao cho $a(r,c)\le a(r,c')$ với mọi $r\in R$.
Cặp yên ngựa(R,C) gọi là tối tiểu nếu mọi cặp yên ngựa(R′,C′) với $R'\subseteq R,C'\subseteq C$ đều có $R'=R,C'=C$. Chứng minh mọi hai cặp tối tiểu có cùng số hàng.