, 2020

Solution 1. We say that a pair ($R', C'$) of nonempty sets is a subpair of a pair ($R, C$) if $R' \subseteq R$ and $C' \subseteq C$. The subpair is proper if at least one of the inclusions is strict.
Let ($R_1, C_1$) and ($R_2, C_2$) be two saddle pairs with $|R_1| > |R_2|$. We will find a saddle subpair ($R', C'$) of ($R_1, C_1$) with $|R'| \leqslant |R_2|$; clearly, this implies the desired statement.

Step 1: We construct maps $\rho: R_1 \rightarrow R_1$ and $\sigma: C_1 \rightarrow C_1$ such that $|\rho(R_1)| \leqslant |R_2|$, and $a(\rho(r_1), c_1) \geqslant a(r_1, \sigma(c_1))$ for all $r_1 \in R_1$ and $c_1 \in C_1$.
Since $(R_1, C_1)$ is a saddle pair, for each $r_2 \in R_2$ there is $r_1 \in R_1$ such that $a(r_1, c_1) \geqslant a(r_2, c_1)$ for all $c_1 \in C_1$; denote one such $r_1$ by $\rho_1(r_2)$. Similarly, we define four functions
$$\begin{align*} & \rho_1: R_2 \rightarrow R_1 \quad \text{such that} \quad a(\rho_1(r_2), c_1) \geqslant a(r_2, c_1) \quad \text{for all} \quad r_2 \in R_2, \quad c_1 \in C_1 ; \\ & \rho_2: R_1 \rightarrow R_2 \quad \text{such that} \quad a(\rho_2(r_1), c_2) \geqslant a(r_1, c_2) \quad \text{for all} \quad r_1 \in R_1, \quad c_2 \in C_2 ; \\ & \sigma_1: C_2 \rightarrow C_1 \quad \text{such that} \quad a(r_1, \sigma_1(c_2)) \leqslant a(r_1, c_2) \quad \text{for all} \quad r_1 \in R_1, \quad c_2 \in C_2 ; \\ & \sigma_2: C_1 \rightarrow C_2 \quad \text{such that} \quad a(r_2, \sigma_2(c_1)) \leqslant a(r_2, c_1) \quad \text{for all} \quad r_2 \in R_2, \quad c_1 \in C_1 . \end{align*}$$
Set now $\rho = \rho_1 \circ \rho_2: R_1 \rightarrow R_1$ and $\sigma = \sigma_1 \circ \sigma_2: C_1 \rightarrow C_1$. We have
$$|\rho(R_1)| = |\rho_1(\rho_2(R_1))| \leqslant |\rho_1(R_2)| \leqslant |R_2| .$$
Moreover, for all $r_1 \in R_1$ and $c_1 \in C_1$, we get
$$\begin{align*} a(\rho(r_1), c_1) = a(\rho_1(\rho_2(r_1)), c_1) \geqslant a(\rho_2(r_1), c_1) & \geqslant a(\rho_2(r_1), \sigma_2(c_1)) \\ & \geqslant a(r_1, \sigma_2(c_1)) \geqslant a(r_1, \sigma_1(\sigma_2(c_1))) = a(r_1, \sigma(c_1)) \end{align*}$$
as desired.

Step 2: Given maps $\rho$ and $\sigma$, we construct a proper saddle subpair $(R', C')$ of $(R_1, C_1)$.
The properties of $\rho$ and $\sigma$ yield that
$$a(\rho^i(r_1), c_1) \geqslant a(\rho^{i-1}(r_1), \sigma(c_1)) \geqslant \ldots \geqslant a(r_1, \sigma^i(c_1)),$$
for each positive integer $i$ and all $r_1 \in R_1, c_1 \in C_1$.
Consider the images $R^i = \rho^i(R_1)$ and $C^i = \sigma^i(C_1)$. Clearly, $R_1 = R^0 \supseteq R^1 \supseteq R^2 \supseteq \ldots$ and $C_1 = C^0 \supseteq C^1 \supseteq C^2 \supseteq \ldots$. Since both chains consist of finite sets, there is an index $n$ such that $R^n = R^{n+1} = \ldots$ and $C^n = C^{n+1} = \ldots$. Then $\rho^n(R^n) = R^{2n} = R^n$, so $\rho^n$ restricted to $R^n$ is a bijection. Similarly, $\sigma^n$ restricted to $C^n$ is a bijection from $C^n$ to itself. Therefore, there exists a positive integer $k$ such that $\rho^{nk}$ acts identically on $R^n$, and $\sigma^{nk}$ acts identically on $C^n$.
We claim now that ($R^n, C^n$) is a saddle subpair of ($R_1, C_1$), with $|R^n| \leqslant |R^1| = |\rho(R_1)| \leqslant |R_2|$, which is what we needed. To check that this is a saddle pair, take any row $r'$, since ($R_1, C_1$) is a saddle pair, there exists $r_1 \in R_1$ such that $a(r_1, c_1) \geqslant a(r', c_1)$ for all $c_1 \in C_1$. Set now $r_* = \rho^{nk}(r_1) \in R^n$. Then, for each $c \in C^n$ we have $c = \sigma^{nk}(c)$ and hence
$$a(r_*, c) = a(\rho^{nk}(r_1), c) \geqslant a(r_1, \sigma^{nk}(c)) = a(r_1, c) \geqslant a(r', c),$$
which establishes condition (i). Condition (ii) is checked similarly.

Solution 2. Denote by $\mathcal{R}$ and $\mathcal{C}$ the set of all rows and the set of all columns of the table, respectively. Let $\mathcal{T}$ denote the given table; for a set $R$ of rows and a set $C$ of columns, let $\mathcal{T}[R, C]$ denote the subtable obtained by intersecting rows from $R$ and columns from $C$.
We say that row $r_1$ exceeds row $r_2$ in range of columns $C$ (where $C \subseteq \mathcal{C}$) and write $r_1 \succeq_C r_2$ or $r_2 \leq_C r_1$, if $a(r_1, c) \geqslant a(r_2, c)$ for all $c \in C$. We say that a row $r_1$ is equal to a row $r_2$ in range of columns $C$ and write $r_1 \equiv_C r_2$, if $a(r_1, c) = a(r_2, c)$ for all $c \in C$. We introduce similar notions, and use the same notation, for columns. Then conditions (i) and (ii) in the definition of a saddle pair can be written as (i) for each $r' \in \mathcal{R}$ there exists $r \in R$ such that $r \geq_C r'$; and (ii) for each $c' \in \mathcal{C}$ there exists $c \in C$ such that $c \leq_R c'$.

Lemma. Suppose that $(R, C)$ is a minimal pair. Remove from the table several rows outside of $R$ and/or several columns outside of $C$. Then ($R, C$) remains a minimal pair in the new table.

Proof. Obviously, $(R, C)$ remains a saddle pair. Suppose $(R', C')$ is a proper subpair of $(R, C)$. Since ($R, C$) is a saddle pair, for each row $r^*$ of the initial table, there is a row $r \in R$ such that $r \geq_C r^*$. If ($R', C'$) became saddle after deleting rows not in $R$ and/or columns not in $C$, there would be a row $r' \in R'$ satisfying $r' \succeq_{C'} r$. Therefore, we would obtain that $r' \succeq_{C'} r^*$, which is exactly condition (i) for the pair ($R', C'$) in the initial table; condition (ii) is checked similarly. Thus, $(R', C')$ was saddle in the initial table, which contradicts the hypothesis that $(R, C)$ was minimal. Hence, ($R, C$) remains minimal after deleting rows and/or columns.

By the Lemma, it suffices to prove the statement of the problem in the case $\mathcal{R} = R_1 \cup R_2$ and $\mathcal{C} = C_1 \cup C_2$. Further, suppose that there exist rows that belong both to $R_1$ and $R_2$. Duplicate every such row, and refer one copy of it to the set $R_1$, and the other copy to the set $R_2$. Then ($R_1, C_1$) and ($R_2, C_2$) will remain minimal pairs in the new table, with the same numbers of rows and columns, but the sets $R_1$ and $R_2$ will become disjoint. Similarly duplicating columns in $C_1 \cap C_2$, we make $C_1$ and $C_2$ disjoint. Thus it is sufficient to prove the required statement in the case $R_1 \cap R_2 = \varnothing$ and $C_1 \cap C_2 = \varnothing$.

The rest of the solution is devoted to the proof of the following claim including the statement of the problem.

Claim. Suppose that ($R_1, C_1$) and ($R_2, C_2$) are minimal pairs in table $\mathcal{T}$ such that $R_2 = \mathcal{R} \setminus R_1$ and $C_2 = \mathcal{C} \setminus C_1$. Then $|R_1| = |R_2|$, $|C_1| = |C_2|$; moreover, there are four bijections
$$\begin{align*} & \rho_1: R_2 \rightarrow R_1 \quad \text{such that} \quad \rho_1(r_2) \equiv_{C_1} r_2 \quad \text{for all} \quad r_2 \in R_2 ; \\ & \rho_2: R_1 \rightarrow R_2 \quad \text{such that} \quad \rho_2(r_1) \equiv_{C_2} r_1 \quad \text{for all} \quad r_1 \in R_1 ; \\ & \sigma_1: C_2 \rightarrow C_1 \quad \text{such that} \quad \sigma_1(c_2) \equiv_{R_1} c_2 \quad \text{for all} \quad c_2 \in C_2 ; \\ & \sigma_2: C_1 \rightarrow C_2 \quad \text{such that} \quad \sigma_2(c_1) \equiv_{R_2} c_1 \quad \text{for all} \quad c_1 \in C_1 . \end{align*}$$

We prove the Claim by induction on $|\mathcal{R}| + |\mathcal{C}|$. In the base case we have $|R_1| = |R_2| = |C_1| = |C_2| = 1$; let $R_i = \{r_i\}$ and $C_i = \{c_i\}$. Since ($R_1, C_1$) and ($R_2, C_2$) are saddle pairs, we have $a(r_1, c_1) \geqslant a(r_2, c_1) \geqslant a(r_2, c_2) \geqslant a(r_1, c_2) \geqslant a(r_1, c_1)$, hence, the table consists of four equal numbers, and the statement follows.

To prove the inductive step, introduce the maps $\rho_1, \rho_2, \sigma_1$, and $\sigma_2$ as in Solution 1, see above. Suppose first that all four maps are surjective. Then, in fact, we have $|R_1| = |R_2|$, $|C_1| = |C_2|$, and all maps are bijective. Moreover, for all $r_2 \in R_2$ and $c_2 \in C_2$ we have
$$\begin{align*} a(r_2, c_2) \leqslant a(r_2, \sigma_2^{-1}(c_2)) \leqslant a(\rho_1(r_2), \sigma_2^{-1}(c_2)) \leqslant a(\rho_1(r_2), \sigma_1^{-1} \circ \sigma_2^{-1}(c_2)) \\ \leqslant a(\rho_2 \circ \rho_1(r_2), \sigma_1^{-1} \circ \sigma_2^{-1}(c_2)) \end{align*}$$
Summing up, we get
$$\sum_{\substack{r_2 \in R_2 \\ c_2 \in C_2}} a(r_2, c_2) \leqslant \sum_{\substack{r_2 \in R_2 \\ c_2 \in C_2}} a(\rho_2 \circ \rho_1(r_2), \sigma_1^{-1} \circ \sigma_2^{-1}(c_2)) .$$
Since $\rho_1 \circ \rho_2$ and $\sigma_1^{-1} \circ \sigma_2^{-1}$ are permutations of $R_2$ and $C_2$, respectively, this inequality is in fact equality. Therefore, all inequalities above turn into equalities, which establishes the inductive step in this case.

It remains to show that all four maps are surjective. For the sake of contradiction, we assume that $\rho_1$ is not surjective. Now let $R_1' = \rho_1(R_2)$ and $C_1' = \sigma_1(C_2)$, and set $R^* = R_1 \setminus R_1'$ and $C^* = C_1 \setminus C_1'$. By our assumption, $R^* \neq \varnothing$.
Let $\mathcal{Q}$ be the table obtained from $\mathcal{T}$ by removing the rows in $R^*$ and the columns in $C^*$; in other words, $\mathcal{Q} = \mathcal{T}[R_1' \cup R_2, C_1' \cup C_2]$. By the definition of $\rho_1$, for each $r_2 \in R_2$ we have $\rho_1(r_2) \geq_{C_1} r_2$, so a fortiori $\rho_1(r_2) \geq_{C_1'} r_2$; moreover, $\rho_1(r_2) \in R_1'$. Similarly, $C_1' \ni \sigma_1(c_2) \leq_{R_1'} c_2$ for each $c_2 \in C_2$. This means that ($R_1', C_1'$) is a saddle pair in $\mathcal{Q}$. Recall that ($R_2, C_2$) remains a minimal pair in $\mathcal{Q}$, due to the Lemma.

Therefore, $\mathcal{Q}$ admits a minimal pair $(\bar{R}_1, \bar{C}_1)$ such that $\bar{R}_1 \subseteq R_1'$ and $\bar{C}_1 \subseteq C_1'$. For a minute, confine ourselves to the subtable $\overline{\mathcal{Q}} = \mathcal{Q}[\bar{R}_1 \cup R_2, \bar{C}_1 \cup C_2]$. By the Lemma, the pairs $(\bar{R}_1, \bar{C}_1)$ and ($R_2, C_2$) are also minimal in $\overline{\mathcal{Q}}$. By the inductive hypothesis, we have $|R_2| = |\bar{R}_1| \leqslant |R_1'| = |\rho_1(R_2)| \leqslant |R_2|$, so all these inequalities are in fact equalities. This implies that $\bar{R}_2 = R_2'$ and that $\rho_1$ is a bijection $R_2 \rightarrow R_1'$. Similarly, $\bar{C}_1 = C_1'$, and $\sigma_1$ is a bijection $C_2 \rightarrow C_1'$. In particular, ($R_1', C_1'$) is a minimal pair in $\mathcal{Q}$.

Now, by inductive hypothesis again, we have $|R_1'| = |R_2|$, $|C_1'| = |C_2|$, and there exist four bijections
$$\begin{array}{lllll} \rho_1': R_2 \rightarrow R_1' & \text{such that} & \rho_1'(r_2) \equiv_{C_1'} r_2 & \text{for all} & r_2 \in R_2 ; \\ \rho_2': R_1' \rightarrow R_2 & \text{such that} & \rho_2'(r_1) \equiv_{C_2} r_1 & \text{for all} & r_1 \in R_1' ; \\ \sigma_1': C_2 \rightarrow C_1' & \text{such that} & \sigma_1'(c_2) \equiv_{R_1'} c_2 & \text{for all} & c_2 \in C_2 ; \\ \sigma_2': C_1' \rightarrow C_2 & \text{such that} & \sigma_2'(c_1) \equiv_{R_2} c_1 & \text{for all} & c_1 \in C_1' . \end{array}$$
Notice here that $\sigma_1$ and $\sigma_1'$ are two bijections $C_2 \rightarrow C_1'$ satisfying $\sigma_1'(c_2) \equiv_{R_1'} c_2 \geq_{R_1} \sigma_1(c_2)$ for all $c_2 \in C_2$. Now, if $\sigma_1'(c_2) \neq \sigma_1(c_2)$ for some $c_2 \in C_2$, then we could remove column $\sigma_1'(c_2)$ from $C_1'$ obtaining another saddle pair $(R_1', C_1' \setminus \{\sigma_1'(c_2)\})$ in $\mathcal{Q}$. This is impossible for a minimal pair ($R_1', C_1'$); hence the maps $\sigma_1$ and $\sigma_1'$ coincide.

Now we are prepared to show that ($R_1', C_1'$) is a saddle pair in $\mathcal{T}$, which yields a desired contradiction (since ($R_1, C_1$) is not minimal). By symmetry, it suffices to find, for each $r' \in \mathcal{R}$, a row $r_1 \in R_1'$ such that $r_1 \geq_{C_1'} r'$. If $r' \in R_2$, then we may put $r_1 = \rho_1(r')$; so, in the sequel we assume $r' \in R_1$.
There exists $r_2 \in R_2$ such that $r' \leq_{C_2} r_2$; set $r_1 = (\rho_2')^{-1}(r_2) \in R_1'$ and recall that $r_1 \equiv_{C_2} r_2 \geq_{C_2} r'$. Therefore, implementing the bijection $\sigma_1 = \sigma_1'$, for each $c_1 \in C_1'$ we get
$$a(r', c_1) \leqslant a(r', \sigma_1^{-1}(c_1)) \leqslant a(r_1, \sigma_1^{-1}(c_1)) = a(r_1, \sigma_1' \circ \sigma_1^{-1}(c_1)) = a(r_1, c_1),$$
which shows $r' \leq_{C_1'} r_1$, as desired. The inductive step is completed.