A $100 \times100$ chessboard has a non-negative real number in each of its cells. A chessboard is balanced if and only if the numbers sum up to one for each column of cells as well as each row of cells. Find the largest positive real number $x$ so that, for any balanced chessboard, we can find $100$ cells of it so that these cells all have number greater or equal to $x$, and no two of these cells are on the same column or row. Proposed by CSJL.
Problem
Source: 2022 Taiwan TST Round 2 Mock Exam Problem 2
Tags: combinatorics, Chessboard, square grid
10.04.2022 14:12
The motivation behind this solution is a classic OI problem: https://tioj.ck.tp.edu.tw/problems/1253 for some constant x, we can color the board with black and white: if the number is less than x, color it white, otherwise color it black. We can then transform the condition into perfect matching of bipartite graph, as follows: construct a bipartite graph G with 100 vertices on each side, the vertices on the left side each represents a row, while the vertices on the right each represents a column, two points (r,c) are connected iff the color on row r, column c is black. It is then trivial to see that, "the set mentioned in the problem exist" iff "G has perfect matching" so if the set doesn't exist, there exist a subset of points on the left side that is a Hall violator of this graph. Now let's consider what does a Hall violator mean in the context of the chessboard. it just means that there exists some subset of rows, call it R, such that if we only consider those rows, and let C be the columns that has a black square in it, then |C| is less than |R|. We take those rows and columns and put it on the top/left side. we can now dissect the board into four parts: (R,C) is the top left, (R,C') is the top right, (R', C) is the bottom left, (R', C') is the bottom right. the sum of numbers in the top right has an upper bound, so the sum of the numbers in the bottom right has a lower bound, so the sum of the numbers in the bottom left has an upper bound, if this upper bound is less than zero, we have a contradiction. It is trivial to write down and solve for the inequality described above, after that we get $x \ge \frac{1}{2550}$, the construction is also trivial and left as an exercise.
11.04.2022 00:44
Replace $100$ with $n$. The answer is $\frac{1}{(\frac{n+1}{2})^2}$ if $n$ is odd and $\frac{1}{\frac n2 \cdot (\frac n2+1)}$ if $n$ is even. Construction: Let $x=\lceil \frac{n+1}{2} \rceil, y=\lfloor \frac{n+1}{2} \rfloor$, then $x+y=n+1$. Let $a_{i,j}$ denote the cell on the $i$th row and $j$th column, where $a_{1,1}$ denotes the top left corner. We have: $a_{i,j}=0$ if $i< y, j< x$ $a_{i,j}=\frac 1x$ if $i\ge y, j<x$ $a_{i,j}=\frac 1y$ if $i<y, j\ge x$ $a_{i,j}=\frac{1}{xy}$ if $i\ge y, j\ge x$ Proof of optimality: Consider a bipartite graph $(R,C)$ such that $R$ is the set of rows, $C$ is the set of columns. Row $i$ and column $j$ are adjacent with an edge if $a_{i,j}\ge \frac{1}{xy}$. We need to prove that this graph has a perfect matching. By Hall, it suffices to show for every $X\subset R$ of rows, $|N(X)|\ge |X|$. Assume for contradiction for a set of $m$ rows (call $r_1,\cdots,r_m$), $|N(X)|\le m-1$. This means there exists at least $n+1-m$ columns, call $c_1,\cdots,c_{n+1-m}$ such that $a_{j,k}<\frac{1}{xy}$ for every $1\le j\le m, 1\le k\le n+1-m$. Let $S$ be the set of squares in the intersection of these $n+1-m$ columns and $m$ rows. It follows that the sum of values of squares in $S$ is at most $(n+1-m)m \frac{1}{xy}< 1$ and equality cannot hold. Let $T$ be the set of squares in the intersection of these $m$ rows but the other $m-1$ columns. Since $S$ and $T$ form $m$ rows, the sum of values of squares in $S$ plus the sum of values of values of squares in $T$ is exactly $m$. It follows that the sum of numbers in squares $S$ is greater than $m-1$. However, $S$ is a subset of $m-1$ columns, absurd!