Conjetura sobre$(0,1)$ - matrices

Question

Deje $A$ ser $m$ por $n$ $(0,1)$-matriz. Para $1\leq i \leq m$ e $1\leq j \leq n$, vamos a $f(A,i,j)$ el número de entradas en $A$ no en la fila $i$, no en la columna $j$, y no es igual a $a_{ij}$.

Me gustaría una prueba o contraejemplo a la siguiente conjetura:

Si $A$ es que no todos los 1 o todos 0, entonces no existe $i$ e $j$ tal que $f(A,i,j)\geq \frac{(m-1)(n-1)-1}{2}$.

Ejemplo 1: Para $A=\begin{bmatrix} 1 & 0 & 1 & 0\\0 & 1 & 0 & 1 \\1 & 0 & 1 & 0\\0 & 1 & 0 & 1 \\\end{bmatrix}$, tenemos $f(A,1,1)=4\geq\frac{3\cdot3-1}{2}$.

Ejemplo 2: Para $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}$, tenemos $f(A,1,2)=6\geq\frac{3\cdot 4-1}{2}$.

Answer 1

Para $m \le n \le 10$, el siguiente más fuerte conjetura es verdadera: $$\min_A \max_{i,j} f(A,i,j) = \left\lceil \frac{(m-1)(n-1)-1}{2} \right\rceil$$

Usted puede resolver este problema a través de programación lineal entera mixta minimizando $z$ sujeto a \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} La primera restricción evita todos los 0 o 1. La segunda restricción exige $z \ge f(A,i,j)$ si $A_{i,j}=0$ y es de otro modo redundante. La tercera restricción exige $z \ge f(A,i,j)$ si $A_{i,j}=1$ y es de otro modo redundante.