Always keep the table valid In a $100\times 100$ table we can "choose" some cells. The table is valid if in each row and each column, the number of chosen cells is between $50$ and $60$, inclusive. Prove that from any valid table, we can get to any other valid table by choosing/unchoosing one cell at a time, so that the table is always valid in between.
We could try to go by induction. Suppose that the statement is true for $(n-1)\times (n-1)$ table and any bounds between $0$ and $n-1$ for validity. Then for an $n\times n$ table, we can perform operations on an $(n-1)\times (n-1)$ table inside it. But then the question is what happens to the remaining row and column - it could be that validity is broken there.
 A: We can do this in two steps:


*

*We can travel between two valid tables in the special case that both have 5000 "chosen" cells.

*From any valid table we can reach some valid table with 5000 "chosen" cells (so every row and column sum is the minimum possible value, 50).


For (1), if the tables are identical we're done. Otherwise we use what a graph theoretic terms is a kind of alternating cycle. For some $n$ there exist distinct cells $(r_1,c_1),(r_2,c_2),\dots,(r_n,c_n)$ "chosen" in the second table and not the first such that $(r_1,c_2),(r_2,c_3),\dots,(r_n,c_1)$ are "chosen" in the first table but not the second. To see this, first pick any $(r_1,c_1)$ "chosen" in the second table but not the first, then pick a $c_2$ such that $(r_1,c_2)$ is "chosen" in the first table but not the second, which exists by the row sum condition, and so on. Eventually this must end up cycling round to $(r_1,c_1).$
Given this sequence, starting with the first table we can: "choose" $(r_1,c_1)$ and $(r_2,c_2),$ then "unchoose" $(r_1,c_2),$ then "choose" $(r_3,c_3),$ then "unchoose" $(r_2,c_3),$ and so on until we finally "unchoose" $(r_{n-1},c_n),$ at which point we finish by "unchoosing" $(r_n,c_1).$ This ends with a new table which has a smaller number of differences with the second table, and still has 5000 "chosen" cells. By repeating this process we eventually reach the second table.
For (2), if we are not done there exists a row $r$ and a column $c$ each with sum greater than $50.$  Let $C$ denote the set of columns $c'$ such that $(r,c')$ is chosen, and let $R$ denote the set of rows $r'$ such that $(r',c)$ is chosen. So $|C|>50$ and $|R|>50.$ If any $c'\in C$ has sum greater than $50,$ we can just "unchoose" $(r,c'),$ and similarly for any $r'\in R$ using $(r',c)$ - this decreases the total number of chosen cells. Otherwise, since all rows in $R'$ and all columns in $C'$ have sum $50,$ there must exist an "unchosen" $(r',c')\in R\times C.$ We can: "choose" $(r',c'),$ then "unchoose" $(r',c)$ and $(r,c').$ This again decreases the total number of "chosen" cells. So eventually we must reach a table with all row and column sums $50.$
