2025 Putnam B4

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}.

$$

对于 $n \geq 2$，令 $A = [a_{i,j}]_{i,j=1}^n$ 为 $n$×$n$ 非负整数矩阵，使得

(a) 当 $i+j\leq n$ 时，$a_{i,j} = 0$；

(b) 当 $1 \leq i \leq n-1$ 和 $1 \leq j \leq n$ 时，$a_{i+1,j} \in \{a_{i,j}, a_{i,j}+1\}$；和

(c) 当 $1 \leq i \leq n$ 和 $1 \leq j \leq n-1$ 时，$a_{i,j+1} \in \{a_{i,j}, a_{i,j}+1\}$。

令 $S$ 为 $A$ 的条目之和，并令 $N$ 为 $A$ 的非零条目数。证明

$$

S \leq \frac{(n+2)N}{3}。

$$