We are given a doubly stochastic matrix of order 100 and need to find the greatest constant λ such that we can select 150 entries in the matrix, and if the other 9850 entries are replaced by 0, the sum of entries in each row and each column is at least λ.
To solve this, we construct a bipartite graph with vertices R={r1,r2,…,r100} representing rows and C={c1,c2,…,c100} representing columns. We draw an edge between rj and ck if xj,k≥λ. The constant λ works if and only if the graph has a matching involving at least 50 rows.
### Proof of Sufficiency
If the graph has a matching A→B where A is a set of 50 rows, then for each row not in A, we add the maximum element in that row (if not already added), and for each column not in B, we add the maximum element in that column. This ensures that we pick at most 150 cells and the sum of elements in any row or column is at least λ.
### Proof of Necessity
We need to show that we can find a matching of 50 in any 150 cells that we pick such that each row and each column has a sum of picked cells at least λ. If rj or ck has exactly one chosen cell, the unique chosen cell on rj or ck is at least λ.
Let S be the set of rows that have exactly one chosen cell, and T be the set of columns that have exactly one cell. Let U be the set of chosen cells in both S and T; let S2 be the set of chosen cells in T but not in S, and T2 be the set of chosen cells in S but not in T. If T2 covers k columns and S2 covers m rows, then there exists a matching of size ∣U∣+k+m. Assume for the sake of contradiction that ∣U∣+k+m≤49.
We focus on the (100−∣U∣)×(100−∣U∣) subgrid where the rows and columns containing elements of U are discarded. Consider the quantity
X=#chosen squares−#rows−#columns+k+m.
Initially, X≥0, implying that the number of chosen squares in this subgrid is at least 2(100−∣U∣)−k−m. This and the number of squares in U give a total of 200−(∣U∣+k+m), so we are done.
### Construction
Let xj,k=0 if 1≤j≤25 and 1≤k≤24,
xj,k=751 if 26≤j≤100 and 1≤k≤24,
xj,k=761 if 1≤j≤25 and 25≤k≤100,
xj,k=190017 if 26≤j≤100 and 25≤k≤100.
We can see that for any λ>190017, the construction fails to meet the conditions.
### Proof of Optimality
Consider a bipartite graph with vertices {r1,…,r100} representing rows and {c1,…,c100} representing columns. Draw an edge between rj and ck if xj,k≥190017. It suffices to prove there exists a matching of size at least 50.
Let S be a set of rows such that ∣N(S)∣−∣S∣ is minimized. We claim ∣N(S)∣−∣S∣≥−50. The set of cells in S∩N(S) has a sum greater than ∣N(S)∣ by algebra.
With this in mind, note that we can biject R∖S to C∖N(S) because if not, the Hall condition is violated. For some T⊂R∖S, there are at most ∣T∣−1 columns in C∖N(S) that have a neighbor in T, then ∣N(S⊔T)∣−∣S⊔T∣=(∣N(S)∣−∣S∣)+(∣N(T)∖N(S)∣−∣T∣)<(∣N(S)∣−∣S∣), contradicting the minimality of ∣N(S)∣−∣S∣. We can also construct an injection from N(S) to S because otherwise, say some U⊂N(S) has ∣N(U)∣<∣U∣, then N(S\N(U))⊂N(S)∖U and we are done by minimality. This allows us to construct a matching of size at least ∣N(S)∣+∣R∖S∣=∣R∣−(∣S∣−∣N(S)∣)=50.
The answer is 190017.