Maths Olympiad Prep

Library / /81 of 97

Algebra Difficulty 8.4 Shortlist Find the answer

Find the greatest constant λ\lambda such that for any doubly stochastic matrix of order 100, we can pick 150150 entries such that if the other 98509850 entries were replaced by 00, the sum of entries in each row and each column is at least λ\lambda.

Note: A doubly stochastic matrix of order nn is a n×nn\times n matrix, all entries are nonnegative reals, and the sum of entries in each row and column is equal to 1.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We are given a doubly stochastic matrix of order 100 and need to find the greatest constant λ\lambda 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 λ\lambda.

To solve this, we construct a bipartite graph with vertices R={r1,r2,,r100}R = \{r_1, r_2, \ldots, r_{100}\} representing rows and C={c1,c2,,c100}C = \{c_1, c_2, \ldots, c_{100}\} representing columns. We draw an edge between rjr_j and ckc_k if xj,kλx_{j,k} \geq \lambda. The constant λ\lambda works if and only if the graph has a matching involving at least 50 rows.

### Proof of Sufficiency
If the graph has a matching ABA \to B where AA is a set of 50 rows, then for each row not in AA, we add the maximum element in that row (if not already added), and for each column not in BB, 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 λ\lambda.

### 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 λ\lambda. If rjr_j or ckc_k has exactly one chosen cell, the unique chosen cell on rjr_j or ckc_k is at least λ\lambda.

Let SS be the set of rows that have exactly one chosen cell, and TT be the set of columns that have exactly one cell. Let UU be the set of chosen cells in both SS and TT; let S2S_2 be the set of chosen cells in TT but not in SS, and T2T_2 be the set of chosen cells in SS but not in TT. If T2T_2 covers kk columns and S2S_2 covers mm rows, then there exists a matching of size U+k+m|U| + k + m. Assume for the sake of contradiction that U+k+m49|U| + k + m \leq 49.

We focus on the (100U)×(100U)(100 - |U|) \times (100 - |U|) subgrid where the rows and columns containing elements of UU are discarded. Consider the quantity
X=#chosen squares#rows#columns+k+m. X = \# \text{chosen squares} - \# \text{rows} - \# \text{columns} + k + m.
Initially, X0X \geq 0, implying that the number of chosen squares in this subgrid is at least 2(100U)km2(100 - |U|) - k - m. This and the number of squares in UU give a total of 200(U+k+m)200 - (|U| + k + m), so we are done.

### Construction
Let xj,k=0x_{j,k} = 0 if 1j251 \leq j \leq 25 and 1k241 \leq k \leq 24,
xj,k=175x_{j,k} = \frac{1}{75} if 26j10026 \leq j \leq 100 and 1k241 \leq k \leq 24,
xj,k=176x_{j,k} = \frac{1}{76} if 1j251 \leq j \leq 25 and 25k10025 \leq k \leq 100,
xj,k=171900x_{j,k} = \frac{17}{1900} if 26j10026 \leq j \leq 100 and 25k10025 \leq k \leq 100.

We can see that for any λ>171900\lambda > \frac{17}{1900}, the construction fails to meet the conditions.

### Proof of Optimality
Consider a bipartite graph with vertices {r1,,r100}\{r_1, \ldots, r_{100}\} representing rows and {c1,,c100}\{c_1, \ldots, c_{100}\} representing columns. Draw an edge between rjr_j and ckc_k if xj,k171900x_{j,k} \geq \frac{17}{1900}. It suffices to prove there exists a matching of size at least 50.

Let SS be a set of rows such that N(S)S|N(S)| - |S| is minimized. We claim N(S)S50|N(S)| - |S| \geq -50. The set of cells in SN(S)S \cap N(S) has a sum greater than N(S)|N(S)| by algebra.

With this in mind, note that we can biject RSR \setminus S to CN(S)C \setminus N(S) because if not, the Hall condition is violated. For some TRST \subset R \setminus S, there are at most T1|T| - 1 columns in CN(S)C \setminus N(S) that have a neighbor in TT, then N(ST)ST=(N(S)S)+(N(T)N(S)T)<(N(S)S)|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|N(S)| - |S|. We can also construct an injection from N(S)N(S) to SS because otherwise, say some UN(S)U \subset N(S) has N(U)<U|N(U)| < |U|, then N(S\N(U))N(S)UN(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)+RS=R(SN(S))=50|N(S)| + |R \setminus S| = |R| - (|S| - |N(S)|) = 50.

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

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.