Maths Olympiad Prep

Library / /7 of 7

Combinatorics Difficulty 9.2 IMO level Prove it China

Find the largest real number λ\lambda with the following property: for any 100th-order doubly stochastic matrix, it is always possible to select 150 elements from it and change the remaining 9850 elements to zero, such that the resulting matrix has row sums and column sums not less than λ\lambda.

Note: An "nnth-order doubly stochastic matrix" is an n×nn \times n square matrix in which all elements are non-negative real numbers, and the sum of each row and the sum of each column are both equal to 1.

Solution

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

First, construct the following doubly stochastic matrix MM: Divide MM into four submatrices, where the first 75 rows and the first 24 columns form submatrix AA, the last 25 rows and the first 24 columns form submatrix BB, the first 75 rows and the last 76 columns form submatrix CC, and the last 25 rows and the last 76 columns form submatrix DD. The elements in AA are all 175\frac{1}{75}, the elements in BB are all 0, the elements in CC are all 171900\frac{17}{1900}, and the elements in DD are all 176\frac{1}{76}. It can be easily verified that MM is a doubly stochastic matrix.

AC
BD

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

To complete the proof, we need to show that λ=171900\lambda = \frac{17}{1900} satisfies the given conditions. Let MM be any doubly stochastic matrix, and we call the elements of MM not less than 171900\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 1100\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 171900\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 kk rows, 51k10051 \le k \le 100, such that the large numbers in these kk rows are distributed among at most k51k - 51 columns.

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

AC
BD

in these submatrices, respectively. The sum of the numbers in the first k51k-51 columns is k51k-51, i.e., S(A)+S(B)=k51S(A) + S(B) = k-51. Since the elements in CC are not large numbers, we have S(C)<171900k(151k)S(C) < \frac{17}{1900}k(151-k). Moreover, S(D)S(B)+S(D)=100kS(D) \le S(B) + S(D) = 100-k. Therefore, we have:
100=S(A)+S(B)+S(C)+S(D)<(k51)+171900k(151k)+(100k)49+1719007576=100, \begin{aligned} 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{aligned}
which is a contradiction.

Thus, we have shown that λmax=171900\lambda_{\max} = \frac{17}{1900} satisfies the given conditions. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.