Putnam 2024, Problem B-1

Let \( n \) and \( k \) be positive integers. The square in the \( i \)th row and \( j \)th column of an \( n \)-by-\( n \) grid contains the number \( i + j - k \). For which \( n \) and \( k \) is it possible to select \( n \) squares from the grid, no two in the same row or column, such that the numbers contained in the selected squares are exactly \( 1, 2, \ldots, n \)?

Solution:
This is possible if and only if $n$ is odd and $k = (n+1)/2$.

We first check that these conditions are necessary. If the pairs $(a_1,b_1),\ldots,(a_n,b_n)$ index squares of the grid with no two in the same row or column, then each of the two sequences $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ is a permutation of $\{1,\ldots,n\}$, and so in particular has sum $1 + \cdots + n = \frac{n(n+1)}{2}$. In particular, if the selected numbers are $1,2,\ldots,n$ in some order, then
$$\frac{n(n+1)}{2} = \sum_{i=1}^{n} (a_i + b_i - k) = \sum_{i=1}^{n} a_i + \sum_{i=1}^{n} b_i - \sum_{i=1}^{n} k = \frac{n(n+1)}{2} + \frac{n(n+1)}{2} - nk$$
which simplifies to $k = (n+1)/2$.

We next check that these conditions are sufficient. For this, it suffices to observe that the sequence
$$\left(1,\frac{n+1}{2}\right),\left(2,\frac{n+3}{2}\right),\ldots,\left(\frac{n+1}{2},n\right),$$
$$\left(\frac{n+3}{2},1\right),\ldots,\left(n,\frac{n-1}{2}\right)$$
of grid entries equals
$$1,3,\ldots,n,2,\ldots,n-1.$$

We illustrate this for the case $n = 5, k = 3$ below; the selected entries are parenthesized.
$$\begin{pmatrix}
-1 & 0 & (1) & 2 & 3 \\
0 & 1 & 2 & (3) & 4 \\
1 & 2 & 3 & 4 & (5) \\
(2) & 3 & 4 & 5 & 6 \\
3 & (4) & 5 & 6 & 7
\end{pmatrix}$$