Consider an $n \times n$ grid ($n \ge 1$) filled with integers so that every row contains each of the numbers $1, 2, \ldots, n$ exactly once, and every column also contains each of $1, 2, \ldots, n$ exactly once — like a completed Sudoku, but without the sub-box constraint (a Latin square). Let $L$ denote the sum of all entries **on or below the main diagonal**, i.e., the sum over cells $(i, j)$ with $i \ge j$, where $i$ is the row index and $j$ is the column index. Prove that for every such grid $$L \;\ge\; \frac{n(n+1)(n+2)}{6},$$ and show that the bound is tight by exhibiting, for every $n$, a grid that attains it. ```hint Slice the triangle by columns Column $j$ meets the lower-triangular region in exactly $n - j + 1$ cells (rows $j$ through $n$), and those cells hold pairwise distinct values from $\{1, \dots, n\}$. What is the smallest possible sum of $n - j + 1$ distinct values from that set? ``` ```hint The closing summation Summing the per-column minimum over all $n$ columns leaves you adding up $n$ consecutive triangular numbers, $\binom{2}{2} + \binom{3}{2} + \cdots + \binom{n+1}{2}$. There is a standard identity for a running sum of triangular numbers — what family of binomial coefficients does it belong to, and what closed form does it collapse to? ``` ```hint Attaining equality For the bound to be tight, the lower part of column $j$ must hold exactly the set $\{1, \dots, n-j+1\}$ for every $j$ simultaneously. Grids whose rows are successive cyclic shifts of one another are a good family to try. ``` ### Constraints & Assumptions - $n$ is an arbitrary positive integer; the inequality must hold for all $n$. - "On or below the main diagonal" includes the diagonal cells $(i, i)$; the region contains $n(n+1)/2$ cells. - Only the row and column permutation properties are assumed — there is no Sudoku box constraint. - A complete answer proves the inequality and demonstrates a grid achieving equality. ### Clarifying Questions to Ask - Does the lower-triangular region include the main diagonal itself, or only the cells strictly below it? - Is the grid constrained in both directions (every row *and* every column is a permutation), or only one? - Am I asked only to prove the inequality, or also to show that the constant cannot be improved? - Is $n$ arbitrary, or fixed (for example $9$, as in actual Sudoku)? ### What a Strong Answer Covers - A decomposition of the lower-triangular region that reduces the global claim to independent local claims (per column or per row). - Correct use of distinctness: the minimum possible sum of $k$ pairwise distinct values from $\{1, \dots, n\}$, applied to each slice, followed by a clean closed-form summation. - Identifying which of the given constraints the inequality actually relies on, and stating the argument at that level of generality. - An explicit construction achieving equality, with verification both that it is a valid grid and that every per-slice minimum is attained simultaneously. ### Follow-up Questions - What is the corresponding tight lower bound for the region *strictly* below the diagonal, and does your construction still achieve it? - What is the maximum possible value of $L$, and how does it follow from your minimum via a symmetry of Latin squares? - Your proof of the inequality likely never used one of the two permutation constraints — which one, and does the tightness construction still need both? - How does the argument adapt to the region on or below the main anti-diagonal?