What is the largest possible ratio $\frac{X}{Y}$?
Short answer: 8/7 based on the matrix
$$\begin{pmatrix}0.5 & 0.5 & 0 \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\end{pmatrix}.$$
for which you get $X=4/3$ and $Y=7/6$ (by coloring the (1,1), (2,2) and (2,3) elements).
How I found this: consider the matrix $A\in\mathbb{R}_+^{2\times k}$ with elements $a_{ij}\geq 0$. We can always permute the columns in a way that the largest numbers are in the first row for the first set of columns, and in the second row for the last set of columns. Let $p$ denote the number of columns for which the maximum is in the first row. We will consider $p=1,2,\ldots,\left \lfloor{k/2}\right \rfloor$ (due to symmetry there is no need to consider larger $p$). We have:
$$X=\sum_{j=1}^p A_{1j} + \sum_{j=p+1}^k A_{2j}.$$
To further reduce symmetry, we can assume that the first $p$ columns and the last $k-p$ columns of $A$ are both sorted high to low in the first row. This symmetry breaking rule is not necessary, but helps in terms of speed (the first one is necessary for efficiently setting $X$).
Let $C \subset \{0,1\}^{2 \times k}$ denote the set of $2^k$ possible colorings: for $c\in C$, $c_{ij} = 1$ if element $(i,j)$ is colored, and 0 otherwise. The following inequalities set the highest lower bound on $Y$ by enumerating all valid colorings:
$$\forall c \in C : (Y \geq \sum_{ij} a_{ij} c_{ij}) \vee \sum_{j} a_{1j} c_{1j} < a_{1j} (1-c_{1j}) - a_{1j'} \forall j' \vee \sum_{j} a_{2j} c_{2j} < a_{2j} (1-c_{2j}) - a_{2j'} \forall j',$$
where $j'$ has to be an uncolored element $(c_{ij'}=0)$.
For fixed $k$, $p$ and $X$, you can minimize $Y$ via mixed integer optimization (matlab/YALMIP code below). It uses a big-M formulation for the three alternatives above. Here is the output for $k=4$:
If you run the code with $k$ larger than 4, you just get extra columns that are zero. Zooming in (generating more data points) shows a maximum at $X=4/3$.
k=5;
eps = 0.0001;
y = [];
for x = linspace(1,1.5,50)
opt = 0;
for p = 1:floor(k/2)
yalmip('clear');
A = sdpvar(2,k);
Y = sdpvar(1,1);
% nonnegative and row sum 1
F = [A >= 0];
F = F + [sum(A,2) == 1];
% break symmetry
F = F + [A(1,1:p) >= A(2,1:p)];
F = F + [A(1,p+1:k) <= A(2,p+1:k)];
F = F + [A(1,1:p-1) >= A(1,2:p)];
F = F + [A(1,p:k-1) >= A(1,p+1:k)];
% set X
X = sum(A(1,1:p)) + sum(A(2,p+1:k));
F = F + [X == x];
% iterate over all colorings
for c = (1 + dec2bin(1:2^k-2) - '0')'
c = full(sparse(c,1:k,ones(k,1),2,k));
% one out of three constraints
one_out_of_three = binvar(3,1);
F = F + [sum(one_out_of_three) == 1];
F = F + [Y >= sum(sum(c.*A)) - k*(1-one_out_of_three(1))];
sum_colored = sum(c.*A,2);
sum_uncolored = sum((1-c).*A,2);
for i = 1:2
for j = find(c(i,:)==0)
F = F + [sum_colored(i) + 0.001 <= sum_uncolored(i) - A(i,j) + k*(1-one_out_of_three(1+i))];
end
end
end
optimize(F,Y, sdpsettings('verbose', 0));
fprintf('Maximum ratio for X=%f, k=%d, p=%d: %f\n', x, k, p, double(X/Y));
opt = max(opt, double(X/Y));
end
y = [y; opt];
end
plot(linspace(1,1.5,50), y, '*');
xlabel('X');
ylabel('max X/Y');
Best Answer
Start with a grid $11\times11$, with $1$ in each square. Total is $22$.
Change $1$ to $-1$ in one square, new total is $18$.
Start with a grid $11\times11$, with random values. Change $1$ value, new total of rows increase or decrease by $2$, new total of columns increase or decrease by $2$, new total of rows+columns change by $-4, 0$ or $+4$.
Total is always equal to $2\pmod 4$. Total cannot be $0$, neither $4$ or $8$ or $12$ ...