China Mathematical Competition (Complementary Test)

Proof of (i). Assume that it is not true. There is a column in $S$ which contains no $u_i$. We may say that $u_i \neq x_{i2}$, $i = 1, 2, 3$. By property (1), we have $u_i < x_{i2}$, $i = 1, 2, 3$. On the other hand, let $k = 2$ in (i). Then by property (O), there exists $i_0 \in \{1, 2, 3\}$ such that $x_{i_0 2} \le u_i$. The contradiction means the assumption is not valid. This completes the proof of (i).

Proof of (ii). By the drawer principle, we know that at least two of the three numbers
$$\min\{x_{11}, x_{12}\}, \min\{x_{21}, x_{22}\}, \min\{x_{31}, x_{32}\}$$
are in the same column. We may say that
$$\min\{x_{21}, x_{22}\} = x_{22}, \min\{x_{31}, x_{32}\} = x_{32}.$$
By (i), we know that the first column of $S$ contains a $u_i$, and it must be $u_1 = x_{11}$; the second column also contains a $u_i$, assuming that it is $u_2 = x_{22}$, and then it must be $u_3 = x_{33}$.
Define $M = \{1, 2, \dots, 9\}$ and
$$I = \{k \in M \mid x_{ik} > \min\{x_{i1}, x_{i2}\}, i = 1, 3\}.$$
Obviously, $I = \{k \in M \mid x_{1k} > x_{11}, x_{3k} > x_{32}\}$, and $1, 2, 3 \notin I$. Since $x_{18}, x_{38} > 1 \ge x_{11}, x_{32}$, we have $8 \in I$. Therefore, $I \ne \emptyset$. Consequently, $\exists k^* \in I$ such that $x_{2k^*} = \max\{x_{2k} \mid k \in I\}$. Of course, $k^* \ne 1, 2, 3$.

We now prove that
$$S' = \begin{bmatrix} x_{11} & x_{12} & x_{1k^*} \\ x_{21} & x_{22} & x_{2k^*} \\ x_{31} & x_{32} & x_{3k^*} \end{bmatrix}$$
has property (O).
By the definition of $I$, we know that
$$x_{1k^*} > x_{11} = u_1, x_{3k^*} > x_{32} \ge u_3.$$
Let $k^* = k$ in $(i)$, and we get $x_{2k^*} \le u_2$ according to property (O) of $S$. Then define
$$u'_1 = u_1, u'_2 = \min\{x_{21}, x_{22}, x_{2k^*}\} = x_{2k^*}, u'_3 = u_3.$$
We claim that, for any $k \in M$, there exists $i \in \{1, 2, 3\}$ such that $u'_i \ge x_{ik}$. Otherwise, we would have $x_{ik} > \min\{x_{i1}, x_{i2}\}$, $i = 1, 3$ and $x_{2k} > x_{2k^*}$, contradicting the definition of $k^*$.
Therefore, $S'$ has property (O).

Secondly, we prove the uniqueness of $S'$. Assume that $\exists k_0 \in M$ such that
$$\hat{S} = \begin{bmatrix} x_{11} & x_{12} & x_{1k_0} \\ x_{21} & x_{22} & x_{2k_0} \\ x_{31} & x_{32} & x_{3k_0} \end{bmatrix}$$
also has property (O). Without loss of generality, we assume that
$$\begin{aligned} u_i &= \min\{x_{i1}, x_{i2}, x_{i3}\} = x_{ii}, \quad i = 1, 2, 3, && (2) \\ x_{32} < x_{31}. \end{aligned}$$
Since $x_{32} < x_{31}$, $x_{22} < x_{21}$, and by (1), we have
$$\hat{u}_1 = \min\{x_{11}, x_{12}, x_{1k_0}\} = x_{11}.$$
By (2) again, we have either
(a) $\hat{u}_3 = \min\{x_{31}, x_{32}, x_{3k_0}\} = x_{3k_0}$ or
(b) $\hat{u}_2 = \min\{x_{21}, x_{22}, x_{2k_0}\} = x_{2k_0}$.
If (a) is true, we will have
$$\hat{u}_1 = x_{11}, \hat{u}_2 = x_{22}, \hat{u}_3 = x_{3k_0}. \quad (3)$$
For $3 \in M$, since both $\hat{S}$ and $S$ have property (O), we will get
$$x_{33} \le \hat{u}_3 = x_{3k_0}, \quad x_{3k_0} \le u_3 = x_{33}.$$
By property (1) of $P$, we have $3 = k_0$. Therefore, $\hat{S} = S$.
If (b) is true, we will have
$$\hat{u}_1 = x_{11}, \hat{u}_2 = x_{2k_0}, \hat{u}_3 = x_{32}. \quad (4)$$
Since $\hat{S}$ has property (O), we know that, for $k^* \in M$, there exists $i \in \{1, 2, 3\}$ such that $\hat{u}_i \ge x_{ik}$. As $k^* \in I$, and by (2), (4), it must be $x_{2k} \le \hat{u}_2 = x_{2k}$.
On the other hand, $S$ also has property (O). Then, in a similar way, we get $x_{2k} \le u'_2 = x_{2k}$.
Therefore, $k^* = k$. This completes the proof.