See this paper. I wonder if this problem was proposed by one of the authors.

ABCDE wrote: See this paper. I wonder if this problem was proposed by one of the authors. Well, this problem was submitted by Thailand and Warut Suksompong is one of the three authors of the paper, so I would assume he proposed it to IMO

Suppose that $(R_1, C_1),\ (R_2, C_2)$ are both saddle pairs with $R_1>R_2$, and I'll find a saddle pair $(R_3, C_3)\subsetneq(R_1, C_1)$ to prove that $(R_1, C_1)$ is not a minimal pair. Let's define two functions as follow: $f: R_1\to R'(\subseteq R_1),\ \forall x\in R_1$, let $y$ be the smallest element in $R_2$ s.t. $a(x, c)\leq a(y, c),\ \forall c\in C_2$, and $f(x)$ be the smallest element in $R_1$ s.t. $a(y, c)\leq a(f(x), c),\ \forall c\in C_1$. $\because |R'|\leq |R_2|<|R_1|$ $\therefore R'\subsetneq R_1$ $g: C_1\to C'(\subseteq C_1),\ \forall x\in C_1$, let $y$ be the smallest element in $C_2$ s.t. $a(r, x)\geq a(r, y),\ \forall r\in R_2$, and $g(x)$ be the smallest element in $C_1$ s.t. $a(r, y)\geq a(r, f(x)),\ \forall r\in R_1$. $\because |R'_n|\leq |R'_{n-1}|$ and $|R'_n|\geq 1$ $\therefore \lim_{n\to\infty}|R'_n|$ converges Similarly, $\lim_{n\to\infty}|C'_n|$ converges. Let $R'_n:=\{f^n(x)|x\in R_1\}$, and $N_R$ be the smallest integer s.t. $|R'_n|=|R'_{n+1}|$ (which means $f:R'_n\to R'_{n+1}$ is bijective), $\forall n\geq N_R$, and define $f^{-1}$ on $R'_{n+1}$. Let $C'_n:=\{g^n(x)|x\in C_1\}$, and $N_C$ be the smallest integer s.t. $|C'_n|=|C'_{n+1}|$ (which means $g:C'_n\to C'_{n+1}$ is bijective), $\forall n\geq N_C$, and define $g^{-1}$ on $C'_{n+1}$. One can easily get that $\forall r\in R'_{n(\geq N_R)}a(r, c)\geq a(f^{-1}(r), g(c))$ and $\forall c\in C'_{n(\geq N_C)}a(r, c)\leq a(f(r), g^{-1}(c))$ $\because$ there are only finite number of sets $R'_n$ $\therefore$ there exists $n_r\in\mathbb N$ s.t. $\forall x\in R'_{n(\geq N_R)},\ f^{n_r}(x)=x$ Define $n_c$ in the same way, and let $m$ be a multiple of $n_rn_c$ s.t. $m>2\max(N_R, N_C)$. Let $R_3=R'_m,\ C_3=C'_m$. $\forall (r, c)\in R_1\times C_3,\ a(r, c)\leq a(f^m(r), (g^{-1})^m(c)=a(f^m(r), c)$, where $(f^m(r), c)\in R_3\times C_3$ $\Rightarrow$ for each row $r'$, one can take $r\in R_1$ s.t. $a(r', c)\leq a(r, c)\leq a(f^m(r), c),\ \forall c\in C_3$, condition (i) holds. Similarly for the column condition (ii) holds. $\therefore(R_3, C_3)$ is a saddle pair. $\because$ for any two saddle pairs there is at least one pair that is not a minimal pair $\therefore$ any two minimal pairs contain the same number of rows.

I hope this works! Let $(R,C)$ be a minimal pair such that $|R|$ is minimal. If this is the only minimal pair, we are done; otherwise let $(R',C')\ne (R,C)$ be another minimal pair; it is enough to show that $|R'| = |R|.$ For every row i(respectively row, column, column) let $f(i)$ be one row (respectively row, column, column) of $R,$ (respecively $R',$ $C,$ $C'$) such that $a(f(i), k)$ is at least (respectively at least, at most, at most) $a(i,k)$ for all $k$ in $C$ (respectively $C',$ $R,$ $R'$.) Clearly if $i \in R$ then $f(i) \in R \Rightarrow f(i) = i$ beacause otherwise we could remove $i$ from $R$ and we would still have a sadlle pair which contradicts minimality. Due to it, we take $f(i) = i, \forall i \in (R\cap R') \cup (C\cap C')$ (note that the above definition of $f$ was ambigous due to points on the intersection, this fixes it). Also, for the same reason we cannot have $f(i) \in R\cap R'$ if $i \in (R\cup R') \setminus (R\cap R').)$ Now note that for any $i\in R$ we have $f(f(i)) \in R$ by definition; hence if we compose $f$ many times, we will eventually find a cycle (that is, we will find some $j \in R$ such that $f^n(j) = j$ for some $n \ge 1.)$ So define the set $A:= \{ i \in R : \exists n \ge 1, f^n(i)=i\};$ by the previous conclusion, we must have $A \ne \emptyset.$ Similarly define the set $B:= \{ j \in C' : \exists n \ge 1, f^n(j)=j\}$ by a similar reason $B \ne \emptyset.$ Note that by definition, $R\cap R' \subseteq A$ and $C \cap C' \subseteq B.$ Claim: The pair $(A,B)$ is a saddle pair. Proof:

Then the set $(A,B)$ is a saddle pair. So let $S \subseteq A$ and $T\subseteq B$ such that $(S,T)$ is a minimal pair. Then $S \subseteq A \subseteq R \Rightarrow |S| \le |R|;$ but rememeber that we have defined $(R,T)$ as the minimal pair with $|R|$ minimal; so we must have $S = R.$ Now we make an similar analysis considering this new minimal pair generated. Replace $(R,C)$ with $(R,T)$ and make similar reasonings. That is, define a function $g(i)$ in a similar way (but for the minimal pairs $(R,T)$ and $(R',C')$). Then define $A':= \{ i \in R' : \exists n \ge 1, {g}^n(i)=i \};$ and $B':= \{ i \in T : \exists n \ge 1, {g}^n(i)=i\}.$ Analogously, we must have that $(A',B')$ is a saddle pair; but by definition $A'\subseteq R'$ and $B' \subseteq T \subseteq C';$ then since $(R',C')$ is a minimal pair, we must have that $A' = R'$ and $B'= C'.$ Henceforward, since $B' \subseteq T \subseteq C'$ we must have $T=C'.$ Now we have two minimal pairs $(R,T) = (R,C')$ and $(R',C');$ and by the previous paragraph, for every $i \in R\cup R'\cup C'$ exists some $n \ge 1$ such that $g^n(i) = i$(refer to this properties as $(\diamondsuit)$). We want to show that $|R|= |R'|;$ it we follow from the above claim. Claim For every $i \in R\setminus (R\cap R')$ we can choose $g(i)$ uniquely, that is, exists only one $j \in R'$ such that $a(j,k) \ge a(i,k), \forall k \in C'$.

Similarly, we can show that for all $i \in R'$ there exist a unique $j \in R$ such that $a(i,k) \ge a(j,k), \forall k \in C'.$ So we have established a bijection between $R$ and $R'. \square.$