Find the greatest constant $\lambda$ such that for any doubly stochastic matrix of order 100, we can pick $150$ entries such that if the other $9850$ entries were replaced by $0$, the sum of entries in each row and each column is at least $\lambda$.
Note: A doubly stochastic matrix of order $n$ is a $n\times n$ matrix, all entries are nonnegative reals, and the sum of entries in each row and column is equal to 1.
Claim: if I construct a bipartite with vertices $R=\{r_1,\cdots,r_{100}\}$ representing rows, $C=\{c_1,\cdots,c_{100}\}$ representing columns. Draw an edge between $r_j$ and $c_k$ if $x_{j,k} \ge l$, then $l$ works if and only if the graph has a matching involving at least 50 rows.
Proof: To see this is sufficient, if the graph has a matching $A\to 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 makes sure we pick at most $150$ cells and the sum of elements in any row or column is at least $l$
To see this is necessary we will prove 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 $l$. Note that if $r_j$ or $c_k$ has exactly one chosen cell, the unique chosen cell on $r_j$ or the unique chosen cell on $c_k$ is at least $l$.
Let $S$ be the set of rows that have exactly 1 chosen cell, $T$ be the set of columns that have exactly 1 cell. Let $U$ be the set of chosen cells in both $S$ and $T$; $S_2$ be the set of chosen cells in $T$ but not in $S$, and $T_2$ be the set of chosen cells in $S$ but not in $T$. If $T_2$ cover $k$ columns and $S_2$ cover $m$ rows then there exists a matching of size $|U| + k + m$. Assume FTSOC $|U|+k+m \le 49$
We focus on the $(100-|U|) \times (100-|U|)$ subgrid where the rows and columns containing elements of $U$ are discarded. Consider the the quantity
$$X = \# \text{ chosen squares } - \# \text{ rows } - \# \text{ columns } + k + m$$
Note all five things in this expression may change from now on as I remove rows or columns. I will show initially $X\ge 0$, which implies 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$ gives a total of $200 - (|U|+k+m)$, so we are done.
Suppose a column has at least two cells in $T_2$. Then we remove the column. Then $X$ decreases by at least $2 - 0 - 1 - 1 - 0 + \text{ additional chosen squares not in S or T }$ (this means $k,m$ decreases as well). Furthermore, for each additional square in that column but not in S, we place a +1 in that row. We can remove rows with at least two cells in $S_2$ similarly.
After doing this process we want to show that ($X$ + number of +1’s assigned) is at least $a+b-k-m$, where we end up with a $a\times b$ subgrid after removals. For each of the $b-k$ columns that are originally not in $T$, the number of +1’s plus number of remaining chosen squares is at least 2. So $X$ + number of +1’s assigned is at least $2(b-k)$. Similarly it is at least $2(a-m)$, so we are done.
The answer is $\frac{17}{1900}$
Construction: let $x_{j,k}=0$ if $1\le j\le 25, 1\le k\le 24$
$x_{j,k}=\frac{1}{75}$ if $26\le j\le 100, 1\le k\le 24$
$x_{j,k}=\frac{1}{76}$ if $1\le j\le 25, 25\le k\le 100$
$x_{j,k}=\frac{17}{1900}$ if $26\le j\le 100, 25\le k\le 100$
We can see that for any $\lambda > \frac{17}{1900}$.
Proof of Optimality:
Consider a bipartite graph with vertices $\{r_1,\cdots,r_{100}\}$ representing rows, $\{c_1,\cdots,c_{100}\}$ representing columns. Draw an edge between $r_j$ and $c_k$ if $x_{j,k} \ge \frac{17}{1900}$. 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. I claim $|N(S)|-|S| \ge -50$
Proof: The set of cells in $S \cap N(S)$ have sum greater than $|N(S)|$ by algebra.
With this in mind, note that we can biject $R\setminus S$ to $C \setminus N(S)$ because if not, hall condition is violated, so for some $T \subset R \setminus S$, there are at most $|T|-1$ columna in $C\backslash N(S)$ that has a neighbour in $T$, then $|N(S\sqcup T)|-|S \sqcup T| =( |N(S)| - |S|) + (|N(T)\setminus 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 otherwise, say some $U\subset N(S)$ has $|N(U)|<|U|$, then $N(S \backslash N(U)) \subset N(S)\setminus U$ and we are done by minimality. This allows us to construct a matching of size at least $|N(S)|+|R\setminus S| = |R| - (|S|-|N(S)|) =50$
CoolJetDude wrote:
50 that was a little difficult
Not really since this is TST 3, I believe the difficulty this day is a lot easier because the previous day is too hard.
The answer is $\lambda_{\max}=\frac{17}{1900}=\frac{51}{75\times 76}. $
Construct a bipartite graph $G=(A,B,E)$ where $A,B$ represents the set of rows and columns. $a_i\sim b_j$ iff the number of grid on $i$-th row and $j$-th column is greater than $\lambda .$ We are done if there exists a $50$-match, since now take the $50$ grid and for the rest $50$ rows and $50$ columns, select the greatest number on it. Then they are no less than $1/100>\lambda $ which satisfies the property.
Now we hope to find the match. FTSOC, by Hall Lemma there exists a set $S\in A$ s.t. $|N(S)|\le |S|-51.$ Let $X=A-X,Y=B-N(S).$ we calculate the sum of numbers on row in $X$ and column in $Y.$ On one hand the sum is no more than $|X|=100-|S|.$ On the other hand since every number in $S\times Y$ is smaller than $\lambda,$ sum of each column of $S\times Y$ is less than $|S|\cdot\lambda .$ So sum in $X\times Y$ is at least $|Y|(1-\lambda|S|)=(100-|N(S)|)(1-\lambda|S|)\ge (151-|S|)(1-\lambda|S|).$ Therefore simple calculation gives $\lambda >\frac{51}{|S|(151-|S|)}\ge\frac{51}{75\times 76},$ contradiction!
Equality can hold when $|S|=75.$ So the maximum value is $\frac{17}{1900}.\Box$