Problem 1840

We begin by proving a lemma on the stability of triangular arrays.

Lemma 3. Let $T$ be a stable triangular array with row sums $s_1, s_2, \dots, s_n$. Then there is a unique index $i$ such $a_{i,n}$ in $T$ can be increased by one to get a new stable triangular array $T^+$ with row sums $s_1, s_2, \dots, s_n + 1$. Additionally, if $s_n > s_{n-1}$, there is also a unique index $j$ such that $a_{j,n}$ in $T$ can be decreased by one to get a new stable triangular array $T^-$ with row sums $s_1, s_2, \dots, s_n - 1$.

*Proof.* For $0 \le i < j \le n-1$ let $x_{i,j} = a_{i,n} - a_{i,j} - a_{j,n}$, and let $x_{j,i} = 1 - x_{i,j}$. Notice that all the $x_{i,j}$ are either 0 or 1 by the fact that $T$ is stable. Consider these as entries of an $n \times n$ matrix $M$ with 0s down the diagonal, we get the adjacency matrix of a complete directed graph (also known as a tournament). Note that if we increase $a_{i,n}$ by 1 for some $i$, this is the same as increasing all $x_{i,k}$ by 1 for all $k \ne i$. This preserves the condition of stable arrays if and only if all $x_{i,k}$ are equal to 0. Likewise, decreasing $a_{j,n}$ by 1 requires all $x_{j,k}$ to be 1. So we must find exactly one column of all 0s and exactly one column of all 1s in $M$, excluding the diagonal entries.

We now show the tournament $M$ is transitive. If for $i < j < k$ we have $x_{i,j} = x_{j,k} = 0$, then
$$0 = x_{i,j} + x_{j,k} = a_{i,n} - a_{i,j} - a_{j,k} - a_{k,n} \ge a_{i,n} - a_{i,k} - a_{k,n} = x_{i,k},$$
so $x_{i,k} = 0$. Similarly, if $x_{i,j} = x_{j,k} = 1$, then
$$2 = x_{i,j} + x_{j,k} = a_{i,n} - a_{i,j} - a_{j,k} - a_{k,n} \le a_{i,n} + 1 - a_{i,k} - a_{k,n} = x_{i,k} + 1,$$
so $x_{i,k} = 1$.

Since this tournament is transitive, it is well-known there exists exactly one $i$ such that $x_{i,k} = 1$ for all $k \neq i$, and likewise exactly one $j$ such that $x_{j,k} = 0$ for all $k \neq j$. These are the desired columns.

It remains only to show that the condition that all the entries are nonnegative is preserved if $s_n > s_{n-1}$; this means we need to show $a_{j,n} > 0$. Suppose $a_{j,n} = 0$. All the other entries of row $n$ are nonnegative integers, this means $a_{j,n}$ will be less than all other elements after the decrement. We also know from above that decreasing $a_{j,n}$ by 1 will preserve the condition of being stable, implying that row $n$ is still non-increasing. Since $a_{j,n}$ will be the minimum after the decrement, $j = n - 1$. This in turn implies that $x_{n-1,k} = 1$ for all $k$, or rather $x_{k,n-1} = 0$ for all $k$. Therefore, $a_{k,n} = a_{k,n-1} + a_{n-1,n} = a_{k,n-1}$. Summing these up for $k$ from 0 to $n - 2$ and remembering that $a_{n-1,n} = 0$, we get $s_{n-1} = s_n$, a contradiction to the assumption that $s_n > s_{n-1}$. So $a_{j,n} > 0$, and the lemma is proven. □

To prove the problem, we induct on $n$. The base case $n = 1$ is clear, since $a_{0,1}$ must be equal to $s_1$. Suppose it is true for $n - 1$, and consider an arbitrary nondecreasing sequence $s_1, s_2, \dots, s_n$. By the inductive hypothesis we can choose a unique $(n-1)$-row stable triangular array with entries $a_{i,j}$ for $0 \le i < j \le n - 1$ that satisfy the row sums $s_1, s_2, \dots, s_{n-1}$. It remains to show there is a unique way to assign the elements of row $n$, namely $a_{i,n}$ for $0 \le i \le n - 1$, to satisfy the row sum $s_n$ while still keeping the array stable.

We now prove that we can uniquely assign row $n$ by another induction on $s_n$. The base case is $s_n = s_{n-1}$. Note that $a_{i,n-1} + a_{n-1,n} \le a_{i,n}$. Summing this up for all $i$ from 0 to $n - 2$ gets that $s_{n-1} + (n-1)a_{n-1,n} \le s_n - a_{n-1,n}$. Since $s_n = s_{n-1}$ and $a_{n-1,n} \ge 0$, we must have equality, so the unique row $n$ that works is $a_{n-1,n} = 0$ and $a_{i,n} = a_{i,n-1}$.

Assume the inductive hypothesis is true for $s_n$. Then we have a unique stable triangular array $T$ with row sums $s_1, s_2, \dots, s_n$. By the Lemma 3, there is a unique way to increment an entry in row $n$ of $T$ to get a new stable triangular array $T^+$ with row sums $s_1, s_2, \dots, s_n + 1$, showing existence. To show uniqueness, suppose we had a second array $T_1^+$. Apply the Lemma 3 to show there is a unique way to decrement an entry in row $n$ to get a new stable triangular array $T_1$ with row sums $s_1, s_2, \dots, s_n$. By the inductive hypothesis, $T = T_1$. We can obtain $T_1^+$ by incrementing an entry of $T_1$, the same as doing the earlier decrement in reverse. We can also obtain $T^+$ by incrementing an entry of $T$. Finally, the statement of the Lemma 3 implies that there is a unique way to increment an entry of $T$ to get a new stable array, so the increments done to $T$ and $T_1$ must have been the same. This shows that $T_1^+ = T^+$, so uniqueness of the stable array with row sums $s_1, s_2, \dots, s_n + 1$ has been shown. This completes both inductions and the proof.