IMO 2020 Shortlist C7
Consider any rectangular table having finitely many rows and columns, with a real number apr,cq in the cell in row r and...
Category: Combinatorics
Problem
Consider any rectangular table having finitely many rows and columns, with a real number apr,cq in the cell in row r and column c. A pair pR,Cq, where R is a set of rows and C a set of columns, is called a saddle pair if the following two conditions are satisfied: piq For each row r1 , there is r P R such that apr,cq ě apr1 ,cq for all c P C; piiq For each column c1 , there is c P C such that apr,cq ď apr,c1 q for all r P R. A saddle pair pR,Cq is called a minimal pair if for each saddle pair pR1 ,C1 q with R1 Ď R and C1 Ď C, we have R1 “ R and C1 “ C. Prove that any two minimal pairs contain the same number of rows. (Thailand)