Putnam 2025, Problem B-4

For \( n \geq 2 \), let \( A = [a_{i,j}]_{i,j=1}^n \) be an \( n \)-by-\( n \) matrix of nonnegative integers such that
(a) \( a_{i,j} = 0 \) when \( i + j \leq n \);
(b) \( a_{i+1,j} \in \{a_{i,j}, a_{i,j} + 1\} \) when \( 1 \leq i \leq n - 1 \) and \( 1 \leq j \leq n \); and
(c) \( a_{i,j+1} \in \{a_{i,j}, a_{i,j} + 1\} \) when \( 1 \leq i \leq n \) and \( 1 \leq j \leq n - 1 \).

Let \( S \) be the sum of the entries of \( A \), and let \( N \) be the number of nonzero entries of \( A \). Prove that
\[
S \leq \frac{(n + 2)N}{3}.
\]

Solution:
**First solution.** For \( i, j \in \{1, \ldots, n\} \), define
\[
d_{i,j} = \min\{|i - i'| + |j - j'| : a_{i',j'} = 0\};
\]
this measures the distance from \( (i, j) \) to the set of \( (i', j') \) where \( a_{i',j'} = 0 \) in the taxicab metric. It follows from conditions (b) and (c) that \( a_{i,j} \leq d_{i,j} \); moreover, \( d_{i,j} \) also satisfies conditions (a)–(c) with the same value of \( N \). Consequently, it is sufficient to prove \( S \leq (n + 2)N/3 \) when \( a_{i,j} = d_{i,j} \) for all \( i, j \), i.e., when \( A \) is a taxicab matrix in addition to satisfying (a)–(c). We will prove this by induction on \( n \), checking the base case \( n = 2 \) by verifying that \( S \leq (n + 2)N/3 \) when \( A \) is one of
\[
\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 2 \end{pmatrix}.
\]
Alternatively, one can extend the problem to \( n = 1 \) by specifying that in that case \( a_{1,1} \in \{0, 1\} \), and then the induction step will also cover \( n = 2 \).

Let \( c_k \) denote the number of entries of \( A \) equal to \( k \). We next prove that \( c_k > c_{k+1} \) for any \( k > 0 \) with \( c_k > 0 \), by showing that the following recipe defines an injective but not surjective map from pairs \( (i, j) \) with \( a_{i,j} = k + 1 \) to pairs \( (i, j) \) with \( a_{i,j} = k \): map \( (i, j) \) to \( (i - 1, j) \) if \( a_{i-1,j} = k \) and to \( (i - 1, j - 1) \) otherwise. To confirm that this map is well-defined, injective, and not surjective, we must check four points.
- The assigned value belongs to \( \{1, \ldots, n\} \times \{1, \ldots, n\} \). This is only an issue when \( i = 1 \) or \( j = 1 \), but in those cases conditions (a)–(c) imply that \( a_{i,j} \leq 1 \). Consequently, we cannot have \( a_{i,j} = k + 1 \) for \( k > 0 \).
- The assigned value \( (i', j') \) satisfies \( a_{i',j'} = k \). This is clear when \( (i', j') = (i - 1, j) \). Otherwise, we have \( a_{i-1,j} = k + 1 \) and \( (i', j') = (i - 1, j - 1) \). Now comparing with \( a_{i,j} \) shows that \( a_{i,j-1} \in \{k, k + 1\} \), but \( a_{i,j-1} = k + 1 \) would force \( a_{i,j} = k + 2 \) because \( A \) is a taxicab matrix; hence \( a_{i,j-1} = k \). Finally, comparing with \( a_{i-1,j} \) and \( a_{i,j-1} \) shows that \( a_{i-1,j-1} = k \).

Returning to the induction step, subtracting 1 from all nonzero entries and deleting the first row and column yields another taxicab matrix. As this operation replaces \( S, N, n \) with \( S - N, N - c_1, n - 1 \) respectively, the induction hypothesis implies that
\[
S - N \leq \frac{n + 1}{3}(N - c_1),
\]
and so it will suffice to prove that
\[
N \leq \frac{N - c_1}{3} + \frac{n + 2}{3} c_1 \Longleftrightarrow 2N \leq (n + 1)c_1.
\]
This is apparent if \( c_1 \geq n \) because \( N \leq \frac{n(n+1)}{2} \). Otherwise, the nonzero values of \( c_k \) form a strictly decreasing sequence starting with \( c_1 \) and summing to \( N \), and so
\[
N \leq \frac{c_1(c_1 + 1)}{2} \leq \frac{(n + 1)c_1}{2}.
\]

**Second solution.** (Art of Problem Solving, user hliu1) Let \( B \) (resp. \( C \)) be the matrix obtained from \( A \) by reversing the nonzero entries in each row (resp. column), keeping the zero entries in the same positions. Since the entries of \( B \) and \( C \) are permutations of the entries of \( A \), the sum of entries of \( A + B + C \) equals \( 3S \).

Since \( a_{i,j} = 0 \) when \( i + j \leq n \) and \( a_{i,j+1}, a_{i+1,j} \leq a_{i,j} + 1 \), by induction on \( i + j \) we obtain
\[
a_{i,j} \neq 0 \implies a_{i,j} \leq i + j - n.
\]
Next, note that the first nonzero entry in each row of \( A \) is 1, so \( b_{i,n} \leq 1 \). Since \( b_{i,j} \leq b_{i,j+1} + 1 \) for \( j < n \),
\[
a_{i,j} \neq 0 \implies b_{i,j} \leq n + 1 - j.
\]
By similar logic with the rows and columns reversed,
\[
a_{i,j} \neq 0 \implies c_{i,j} \leq n + 1 - i.
\]
Summing yields
\[
a_{i,j} \neq 0 \implies a_{i,j} + b_{i,j} + c_{i,j} \leq n + 2.
\]
Now summing over the nonzero entries of \( A + B + C \) yields \( 3S \leq (n + 2)N \) as desired.

**Remark.** The second solution gives rise to an analogous statement about \( k \)-dimensional arrays of nonnegative integers for any \( k \).