Problem: Let $n$ be a positive integer.
Consider a triangular array of nonnegative integers as follows:
\begin{center}
\begin{asy}
  size(8cm);
  defaultpen(fontsize(10pt));
  label(scale(0.8)*"Row $1$:", (-6, 2.9));
  label(scale(0.8)*"Row $2$:", (-6, 2.2));
  label(scale(0.8)*"$\vdots$", (-6, 1.5));
  label(scale(0.8)*"Row $n-1$:", (-6, 0.8));
  label(scale(0.8)*"Row $n$:", (-6, 0.1));

  label("$a_{0,1}$", (0,2.8));

  label("$a_{0,2}$", (-1,2.1));
  label("$a_{1,2}$", ( 1,2.1));

  label(rotate(90)*"$\ddots$", (-2,1.5));
  label("$\vdots$", ( 0,1.5));
  label("$\ddots$", ( 2,1.5));

  label("$a_{0,n-1}$", (-3,0.7));
  label("$a_{1,n-1}$", (-1,0.7));
  label("$\dots$", (1,0.7));
  label("$a_{n-2,n-1}$", (3,0.7));

  label("$a_{0,n}$", (-4,0));
  label("$a_{1,n}$", (-2,0));
  label("$a_{2,n}$", (-0,0));
  label("$\dots$", (2,0));
  label("$a_{n-1,n}$", (4,0));
\end{asy}
\end{center}
Call such a triangular array \textit{stable} if for every $0 \le i < j < k \le n$ we have
\[ a_{i,j} + a_{j,k} \le a_{i,k} \le a_{i,j} + a_{j,k} + 1. \]
For $s_1$, \dots, $s_n$ any nondecreasing sequence of nonnegative integers,
prove that there exists a unique stable triangular array such that
the sum of all of the entries in row $k$ is equal to $s_k$.

Solution: Firstly, here are illustrative examples showing the arrays
for $(s_1, s_2, s_3, s_4) = (2, 5, 9, x)$ where $9 \le x \le 14$.
(The array has been left justified.)
\[
  \begin{bmatrix}
    2 & \swarrow \\
    4 & 1 & \swarrow \\
    5 & 3 & 1 & \swarrow \\
    5 & 3 & 1 & 0
  \end{bmatrix}
  \begin{bmatrix}
    2 & \swarrow \\
    4 & 1 & \swarrow \\
    5 & 3 & 1 & \swarrow \\
    \mathbf{\color{red} 6} & 3 & 1 & 0
  \end{bmatrix}
  \begin{bmatrix}
    2 & \swarrow \\
    4 & 1 & \swarrow \\
    5 & 3 & 1 & \swarrow \\
    6 & 3 & \mathbf{\color{red} 2} & 0
  \end{bmatrix}
\]
\[
  \begin{bmatrix}
    2 & \swarrow \\
    4 & 1 & \swarrow \\
    5 & 3 & 1 & \swarrow \\
    6 & \mathbf{\color{red} 4} & 2 & 0
  \end{bmatrix}
  \begin{bmatrix}
    2 & \swarrow \\
    4 & 1 & \swarrow \\
    5 & 3 & 1 & \swarrow \\
    6 & 4 & 2 & \mathbf{\color{red} 1}
  \end{bmatrix}
  \begin{bmatrix}
    2 & \swarrow \\
    4 & 1 & \swarrow \\
    5 & 3 & 1 & \swarrow \\
    \mathbf{\color{red} 7} & 4 & 2 & 1
  \end{bmatrix}
\]


Now we outline the proof.
By induction on $n$, we may assume the first $n-1$ rows are fixed.
Now, let $N = s_n$ vary.
Now, we prove our result by (another) induction on $N \ge s_{n-1}$.

The base case $N = s_{n-1}$ is done by copying
the $n-1$st row and adding a zero at the end.
This is also unique,
since $a_{i,n} \ge a_{i-1,n} + a_{n-1,n}$ for all $i=0, \dots, n-2$,
whence $\sum a_{i,n} \ge s_{n-1}$ follows.

Now the inductive step is based on the following lemma,
which illustrates the idea of a ``unique increasable entry''.
\begin{lemma*}
  Fix a stable array
  Construct a tournament on the $n$ entries
  of the last row as follows: for $i < j$,
  \begin{itemize}
    \ii $a_{i,n} \to a_{j,n}$
    if $a_{i,n} = a_{i,j} + a_{j,n}$, and
    \ii $a_{j,n} \to a_{i,n}$
    if $a_{i,n} = a_{i,j} + a_{j,n} + 1$.
  \end{itemize}
  Then this tournament is transitive.
  Also, except for $N = s_{n-1}$, a $0$ entry is never a source.
\end{lemma*}
Intuitively, $a_{i,n} \to a_{j,n}$
if $a_{i,n}$ blocks $a_{j,n}$ from increasing.
For instance, in the example
\[
  \begin{bmatrix}
    2 & \swarrow \\
    4 & 1 & \swarrow \\
    5 & 3 & 1 & \swarrow \\
    \mathbf 6 & 3 & 1 & 0
  \end{bmatrix}
\]
the tournament is $1 \to 3 \to 0 \to 6$.
\begin{proof}
  [Proof of lemma]
  Let $0 \le i < j < k < n$ be indices.
  Let $x = a_{i,n}$, $y = a_{j,n}$, $z = a_{k,n}$,
  $p = a_{i,j}$, $s = a_{i,k}$, $q = a_{j,k}$. Picture:
  \[
    \begin{bmatrix}
      p & \swarrow \\
      s & q & \swarrow \\
      x & y & z
    \end{bmatrix}
  \]
  If $x \to y \to z \to x$ happens, that means
  $x = y+p$, $y = q+z$, $x = s+z+1$,
  which gives $s=p+q-1$, contradiction.
  Similarly if $x \leftarrow y \leftarrow z \leftarrow x$ then
  $x = y+p+1$, $y = q+z+1$, $x = s+z$,
  which gives $s=p+q+2$, also contradiction.
\end{proof}

Now this allows us to perform our induction.
Indeed, to show existence from $N$ to $N+1$
we take a source of the tournament above and increase it.
Conversely, to show uniqueness for $N$,
note that we can take the (nonzero) sink of the tournament and decrement it,
which gives $N-1$; our uniqueness inductive hypothesis now finishes.

\begin{remark*}
  Colin Tang found a nice proof of uniqueness:
  \[
    s_k + \sum_{i=1}^{k-1} a_{0,i} \le ka_{0,k}
    \le s_k + \sum_{i=1} \left( a_{0,i} + 1 \right)
  \]
  and similarly for other entries.
\end{remark*}