Problem

Source: 2022 Taiwan TST Round 2 Mock Exam Problem 2

Tags: combinatorics, Chessboard, square grid



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.