insane problem

I just spent eleven hours on this. Bruh... Remove columns and rows with no red cells, and suppose there are $m$ columns in the original grid. First, suppose there are exactly $s$ rows having the same number of red cells $k$, then none of their cells can share a column since otherwise, those two cells fail. Now, we merge all of these rows into a single row, which we say has identity equal to $k$ and size equal to $sk$. Notice this preserves the number of red cells in each column. We repeat this operation for all values of $k$ in rows and then repeat this operation for all the columns as well. Finally, we sort the rows in the order of size so that the top row is the largest and the bottom row is the smallest. Then, we sort the columns so that the leftmost column is the largest and the rightmost is the smallest. We call this new grid the reduced table. Let the total number of rows in the reduced table be $n$. Then there exists a row with identity at least $n$, so there is a row with at least $n$ elements. Thus there are at least $n$ columns. By symmetry, the number of rows is also at least the number of columns, so there are exactly $n$ columns, and thus the identity of the largest row is exactly $n$, so the set of identities of the rows and of the columns are exactly equal to $\{1, 2, 3, \ldots, n\}$. Now notice that for each value $1 \leq i \leq n$, the columns with identity in $\{i, i+1, \ldots, n\}$ must have size at least $i$, so there are at least $n-i+1$ such rows. Thus, we can choose the largest column with size at least $n$ to be $c_n$, then a distinct column with the largest size at least $n-1$ to be $c_{n-1}$, and so on until we have chosen a distinct column for each $i$ which has size at least $i$. We let $c_i$ be the column chosen to have size at least $i$, and we have that the sizes of $c_1, c_2, \ldots, c_n$ are in increasing order (right to left). Now we define $\text{id}(i), \text{size}(i)$ to be the identity and size of column $c_i$ respectively. Since the set of identities is exactly $\{1, 2, \ldots, n\}$, it follows that $\text{id}$ is a permutation. Now notice that if there are $n$ column in the reduced table, then $$m \geq n + \sum \limits_{i = 1}^n \left( \frac{\text{size}(i)}{\text{id}(i)} - 1 \right) = n + \sum \limits_{i = 1}^n \left \lceil \frac{\text{size}(i)}{\text{id}(i)} - 1 \right \rceil \geq n + \sum \limits_{i = 1}^n \left \lceil \frac{\text{size}(i)}{\text{id}(i)} - 1 \right \rceil \geq n + \sum \limits_{i = 1}^n \log_2 \left( \frac{\text{size}(i)}{\text{id}(i)} \right)$$ Thus, it follows that $m \geq n + \sum \limits_{i = 1}^n \log_2 \left (\frac{\text{size}(i)}{i} \right) + \sum \limits_{i = 1}^n \log_2 \left(\frac{i}{\text{id}(i)} \right) \geq n + \sum \limits_{i = 1}^n \log_2 \left (\frac{\text{size}(i)}{i} \right)$ Finally, notice that in all of the above claims if we remove the $k$ rightmost elements of the row with identity $k$ (has size at least $2k \leq n$), so repeat the process of choosing $c_i$ without those $k$ elements, and let the set of columns those elements lie in be numbered $a_1 < a_2 < \cdots < a_k \leq n-k$. Then for each $a_i$, it follows that $\text{size}(a_i) \geq a_i + 1$, so $$m \geq n + \sum \limits_{i = 1}^k \log_2 \left (\frac{a_i+1}{a_i} \right) \geq \sum \limits_{i = n-2k+1}^{n-k} \log_2 \left (\frac{i+1}{i} \right) = n + \log_2 \left( \frac{n-k+1}{n-2k+1} \right)$$ This value is smallest when $n = 2k$, where we have the lower bound $m \geq 2k + \lceil \log_2 (k+1) \rceil$. Thus it follows that for $m = 70$, the maximal value of $k$ is $\boxed{32}$. I can't be bothered to draw it out, but it turned out to be identical to the picture in the above post. The same construction proves the exactness of the bound for all $k$, funnily enough.

Nice Problem, Last writeup of 2024! The answer is $2k+\lceil\left(\log_2 (k+1)\right)\rceil$ for $n=2k$ We local spam. My construction is the same as in #2.