Sum and minimum in $3\times 3$ table

combinatoricsextremal-combinatorics

A $3\times 3$ table is filled with non-negative real numbers so that each row sums to $1$. A subset of cells is called admissible if it has size $3$ and the three cells all lie in different rows and columns. For each admissible set $A$, let $s(A)$ be the sum of the numbers in the three cells and $m(A)$ be the minimum of those numbers.

There must be an admissible set $A$ with $s(A)\geq 1$. (Just take three disjoint admissible sets; since the total sum is $3$, one set must have sum at least $1$.) Is it true that there is always an admissible set $A$ such that $s(A)\geq 1$, and $m(A)$ is the highest among all admissible sets?

Best Answer

Yes, this is true. Take $A$ to be an admissible set achieving the highest possible $m(A),$ but subject to that condition, with the minimum achievable number of cells equal to $m(A).$ (So we prefer one entry to equal $m(A)$ rather than two.)

Without loss of generality, $A$ is the set of diagonal cells, and the $(1,1)$ cell is $m(A).$ Consider which cells are not in $A$ but are strictly greater than $m(A).$ Call these "augmenting".

If there is a row with no augmenting cells, then the element of $A$ in that row is at least $1-2m(A),$ which gives $s(A)\geq 1.$ So we are done unless each row has an augmenting cell.

If the $(2,1)$ and $(3,1)$ cells are not augmenting, then the total of the cells in the $(2,2),(2,3),(3,2),(3,3)$ positions is at least $2-2m(A).$ Therefore either of $\{(1,1),(2,2),(3,3)\}$ or $\{(1,1),(2,3),(3,2)\}$ has sum at least $1,$ and by the previous paragraph these both have minimum at least $m(A),$ so we're done.

The remaining case is that one of the $(2,1)$ or $(3,1)$ cells is augmenting. Some cell in the first row is also augmenting. If $(1,2)$ and $(2,1)$ are augmenting then the set $(1,2),(2,1),(3,3)$ is an admissible set contradicting the choice of $A$ - it either has a higher minimum or the same minimum but fewer elements achieving the minimum. Similarly we are done if $(1,3)$ and $(3,1)$ are augmenting. Otherwise wlog $(2,1),(1,3)$ are augmenting and $(3,1),(1,2)$ are not (the other case just swaps $2$ and $3$). Then $(3,2)$ must be augmenting because it is the only remaining cell in the third row, so $(2,1),(1,3),(3,2)$ forms an admissible set with higher minimum.

Related Solutions

Choosing columns in array

Yes, we can.

Let $P(n)$ be as follows :

$P(n)$ : In the $4\times n$ array, we can choose some columns in such a way that for at least three rows, the number of chosen marked cells and the number of unchosen marked cells differ by at most $1$.

In the following, $[a,b]$ represents the cell in the $a$-th row and in the $b$-th column. Also, $[a,b]=[c,d]$ means that either that both $[a,b]$ and $[c,d]$ are marked or that both $[a,b]$ and $[c,d]$ are unmarked.

Claim : If $P(7),P(8)$ are true, then $P(n)$ is true for all $n\ge 9$.

Proof :

There are $2^3=8$ possibilities for three cells to be marked or unmarked. So, if $n\ge 9$, then, by the pigeonhole principle, there is at least one pair of distinct integers $(s,t)$ such that $[1,s]=[1,t],$$[2,s]=[2,t]$ and $[3,s]=[3,t]$. We may suppose that $[1,1]=[1,2],$$[2,1]=[2,2]$ and $[3,1]=[3,2]$. Now, consider the $4\times (n-2)$ array made by the $(n-2)$ columns from the third to the $n$-th. Suppose that $P(n-2)$ is true. Then, we can choose some columns (call them $p$ columns) which satisfy our condition. Now, let us come back to the $4\times n$ array. If choosing the first column and the $p$ columns works, then we are done. If it doesn't work, then choosing the second column and the $p$ columns works. So, $P(n)$ is true. $\quad\square$

In the following, let us prove that $P(1),P(2),\cdots,P(8)$ are true.

We use the following two lemmas (the proofs are written at the end of the answer) :

Lemma 1 : If $P(n-1)$ is true and there is at least one column whose four cells are unmarked, then $P(n)$ is true.

Lemma 2 : If $P(n-2)$ is true and there is a pair of distinct integers $(s,t)$ such that at least three of $[i,s]=[i,t]\ (i=1,2,3,4)$ hold, then $P(n)$ is true.

From the lemmas,

$\ \ (\star)$ : we may suppose that there is at least one marked cell in each column and that there is no pair of distinct integers $(s,t)$ such that at least three of $[i,s]=[i,t]\ (i=1,2,3,4)$ hold.

This $(\star)$ reduces the number of cases to consider.

For $n=1$, we can choose the column.
For $n=2$, we can choose the first column.
For $n=3$, if choosing the first and the second columns works, then we are done. If it doesn't work, then we may suppose that $[1,1],[1,2],[2,1],[2,2],[3,1]$ are marked and $[1,3],[2,3],[3,2]$ are unmarked. Then, choosing the first column works.
For $n=4$, if there is a pair of distinct integers $(s,t)$ such that $[1,s]=[1,t]$ and $[2,s]=[2,t]$, then we may suppose that $[3,s]$ is marked and that $[3,t]$ is unmarked.
case 1 : If $[3,u]=[3,v]$ where $u\not=v$ are different from $s$ and $t$, then choosing the $s$-th and the $u$-th columns works.
case 2 : If $[3,u]$ is marked and $[3,v]$ is unmarked, then choosing the $s$-th and the $v$-th columns works.
If there is no pair of distinct integers $(s,t)$ such that $[1,s]=[1,t]$ and $[2,s]=[2,t]$, then we may suppose that $[1,1],[1,3],[2,1],[2,4]$ are marked and $[1,2],[1,4],[2,2],[2,3]$ are unmarked. If choosing the first and the second columns works, then we are done. If it doesn't work, then from $(\star)$, choosing the first column works.
For $n=5$, if there are two distinct pairs of distinct integers $(s,t),(u,v)$ such that $[1,s]=[1,t],$$[2,s]=[2,t],$$[1,u]=[1,v]$ and $[2,u]=[2,v]$, then choosing the $s$-th and the $v$-th columns works.
If there is only one pair of distinct integers $(s,t)$ such that $[1,s]=[1,t]$ and $[2,s]=[2,t]$, then we may suppose that we have the following three cases :
case 1 : $[1,1],[1,2],[2,1],[2,2],[3,1]$ are marked and $[3,2],[1,5],[2,5]$ are unmarked. If choosing the first and the third columns works, then we are done. If it doesn't workd, then choosing the second and the third columns works.
case 2 : $[1,1],[1,2],[1,3],[2,3],[2,4],[3,1]$ are marked and $[1,4],[1,5],[2,1],[2,2],[3,2]$ are unmarked. If choosing the first and the third columns works, then we are done. If it doesn't work, then choosing the second and the third columns works.
case 3 : $[1,3],[1,5],[2,4],[2,5],[3,1]$ are marked and $[1,1],[1,2],[1,4],[2,1],[2,2],[2,3],[3,2]$ are unmarked. If choosing the first and the third and the fourth columns workds, then we are done. If it doesn't work, then choosing the first and the fifth columns works.
For $n=6$, we may suppose that there are two distinct pairs of distinct integers $(s,t),(u,v)$ such that $[1,s]=[1,t],$$[2,s]=[2,t],$$[1,u]=[1,v]$ and $[2,u]=[2,v]$. Then, we may suppose that $[3,s],[3,u]$ are marked and that $[3,t],[3,v]$ are unmarked. Now, choosing the $s$-th and the $v$-th and the one from the rest two columns works.
For $n=7$, we may suppose that there are three distinct pairs of distinct integers $(a,b),(c,d),(e,f)$ such that $[1,a]=[1,b],$$[2,a]=[2,b],$$[1,c]=[1,d],$$[2,c]=[2,d],$$[1,e]=[1,f]$ and $[2,e]=[2,f]$. Then, we may suppose that $[3,a],[3,c],[3,e]$ are marked and that $[3,b],[3,d],[3,f]$ are unmarked. If $[3,g]$ is marked where $g$ is different from $a,b,c,d,e$ and $f$, then choosing the $a$-th, the $c$-th and the $f$-th columns works. If $[3,g]$ is unmarked, then choosing the $a$-th , the $d$-th and the $f$-th columns works.
For $n=8$, we may suppose that there are four distinct pairs of distinct integers $(a,b),(c,d),(e,f),(g,h)$ such that $[1,a]=[1,b],$$[2,a]=[2,b],$$[1,c]=[1,d],$$[2,c]=[2,d],$$[1,e]=[1,f],$$[2,e]=[2,f],$$[1,g]=[1,h]$ and $[2,g]=[2,h]$. Then, we may suppose that $[3,a],[3,c],[3,e],[3,g]$ are marked and that $[3,b],[3,d],[3,f],[3,h]$ are unmarked. Now, choosing the $a$-th, the $d$-th, the $e$-th and the $h$-th columns works.

Finally, let us prove the two lemmas :

Lemma 1 : If $P(n-1)$ is true and there is at least one column whose four cells are unmarked, then $P(n)$ is true.

Proof for Lemma 1 :

Consider the $4\times (n-1)$ array excluding the column. Since $P(n-1)$ is true, we can choose suitable columns (call them $p$ columns) for the $4\times (n-1)$ array. Now, coming back to the $4\times n$ array, we see that choosing the $p$ columns works. $\quad\square$

Lemma 2 : If $P(n-2)$ is true and there is a pair of distinct integers $(s,t)$ such that at least three of $[i,s]=[i,t]\ (i=1,2,3,4)$ hold, then $P(n)$ is true.

Proof for Lemma 2 :

Consider the $4\times (n-2)$ array excluding the $s$-th and the $t$-th columns. Since $P(n-2)$ is true, we can choose suitable columns (call them $p$ columns) for the $4\times (n-2)$ array. Now, let us come back to the $4\times n$ array. If choosing the $s$-th column and the $p$ columns works, then we are done. If it doesn't work, then choosing the $t$-th column and the $p$ columns works. $\quad\square$

Ratio of maximum sums in table

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

Related Solutions

Choosing columns in array

Ratio of maximum sums in table

Related Question