Let $A$ be an $m$ by $n$ $(0,1)$-matrix. For $1\leq i \leq m$ and $1\leq j \leq n$, let $f(A,i,j)$ be the number of entries in $A$ not in row $i$, not in column $j$, and not equal to $a_{ij}$.
I would like a proof or counterexample to the following conjecture:
If $A$ is not all 1's or all 0's, then there exist $i$ and $j$ such that $f(A,i,j)\geq \frac{(m-1)(n-1)-1}{2}$.
Example 1: For $A=\begin{bmatrix} 1 & 0 & 1 & 0\\0 & 1 & 0 & 1 \\1 & 0 & 1 & 0\\0 & 1 & 0 & 1 \\\end{bmatrix}$, we have $f(A,1,1)=4\geq\frac{3\cdot3-1}{2}$.
Example 2: For $A=\begin{bmatrix} 0 & 1 & 0 & 0 & 1\\1 & 0 & 0 & 1 & 0 \\1 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 0 & 1\\\end{bmatrix}$, we have $f(A,1,2)=6\geq\frac{3\cdot 4-1}{2}$.
For $m \le n \le 10$, the following stronger conjecture is true: $$\min_A \max_{i,j} f(A,i,j) = \left\lceil \frac{(m-1)(n-1)-1}{2} \right\rceil$$
You can solve this problem via mixed integer linear programming by minimizing $z$ subject to \begin{align} 1 \le \sum_{i,j} A_{i,j} &\le mn-1 \\ \sum_{k \not= i} \sum_{\ell \not=j} A_{k,\ell} - z &\le (m-1)(n-1)A_{i,j} \\ \sum_{k \not= i} \sum_{\ell \not=j} (1-A_{k,\ell}) - z &\le (m-1)(n-1)(1-A_{i,j}) \\ A_{i,j} &\in\{0,1\} \end{align} The first constraint avoids all 0 or all 1. The second constraint enforces $z \ge f(A,i,j)$ if $A_{i,j}=0$ and is otherwise redundant. The third constraint enforces $z \ge f(A,i,j)$ if $A_{i,j}=1$ and is otherwise redundant.