China-TST-2023B

Proof. The answer is $\frac{17}{1900}$.

First, construct the following doubly stochastic matrix $M$: Divide $M$ into four submatrices, where the first 75 rows and the first 24 columns form submatrix $A$, the last 25 rows and the first 24 columns form submatrix $B$, the first 75 rows and the last 76 columns form submatrix $C$, and the last 25 rows and the last 76 columns form submatrix $D$. The elements in $A$ are all $\frac{1}{75}$, the elements in $B$ are all 0, the elements in $C$ are all $\frac{17}{1900}$, and the elements in $D$ are all $\frac{1}{76}$. It can be easily verified that $M$ is a doubly stochastic matrix.

A	C
B	D

Assume that we can select 150 elements from $M$ such that the sum of the selected elements in each row and each column is greater than $\frac{17}{1900}$. Let $a$ be the number of elements selected from $A$ and $d$ be the number of elements selected from $D$. In the first 75 rows and the last 76 columns, there are at least $151-a-d$ rows and columns that do not contain selected elements from $A$ or $D$. Among these rows and columns, there must be at least 2 selected elements from $C$, as each selected element from $C$ contributes to exactly one row and one column. Therefore, the number of selected elements from $C$ is at least $2\cdot (151-a-d)\cdot \frac{1}{2}=151-a-d$. Thus, the total number of selected elements from $A,C,D$ is at least $a+d+(151-a-d)=151$, which is a contradiction. Hence, $\lambda \le \frac{17}{1900}$.

To complete the proof, we need to show that $\lambda =\frac{17}{1900}$ satisfies the given conditions. Let $M$ be any doubly stochastic matrix, and we call the elements of $M$ not less than $\frac{17}{1900}$ "large numbers".

If there exist 50 distinct large numbers that are not in the same row or column, we can assume that these 50 large numbers are in the first 50 rows and the first 50 columns by exchanging rows and columns if necessary. Then, we select the largest element from each of the last 50 rows (which is not less than $\frac{1}{100}$) and the largest element from each of the last 50 columns. In this way, we have selected at most 150 numbers, and the sum of the selected numbers in each row and each column is not less than $\frac{17}{1900}$.

We now show that the above scenario always occurs. By contradiction, assume that there are no 50 distinct large numbers that are not in the same row or column. Then, by Hall's theorem in the deficiency form, we have: (*) There exist $k$ rows, $51\le k\le 100$, such that the large numbers in these $k$ rows are distributed among at most $k-51$ columns.

Without loss of generality, assume that the large numbers in the first $k$ rows are distributed among the first $k-51$ columns. Divide $M$ into four submatrices using the first $k$ rows and the first $k-51$ columns, similar to the construction in the previous proof, and denote them as $A,B,C,D$. Let $S(A),S(B),S(C),S(D)$ be the sums of the elements

A	C
B	D

in these submatrices, respectively. The sum of the numbers in the first $k-51$ columns is $k-51$, i.e., $S(A)+S(B)=k-51$. Since the elements in $C$ are not large numbers, we have $S(C)<\frac{17}{1900}k(151-k)$. Moreover, $S(D)\le S(B)+S(D)=100-k$. Therefore, we have: $$\begin{array}{rl}100& =S(A)+S(B)+S(C)+S(D)\\ & <(k-51)+\frac{17}{1900}k(151-k)+(100-k)\\ & \le 49+\frac{17}{1900}\cdot 75\cdot 76=100,\end{array}$$ which is a contradiction.

Thus, we have shown that ${\lambda }_{\max }=\frac{17}{1900}$ satisfies the given conditions. $\square$