Kvant Math Problem 1472

Verified: yes
Verdicts: PASS + PASS
Solve time: 17m50s
Source on kvant.digital

Problem

For which natural $n\gt 1$ can one choose $n$ distinct numbers in the table, each from different rows and different columns? $$\begin{array}{cccccc} 1&2&3&\ldots&n-1&n\ n&1&2&\ldots&n-2&n-1\ n-1&n&1&\ldots&n-3&n-2\ &&&\mathclap{........................~.}&&\ 2&3&4&\ldots&n&1 \end{array}$$

A. P. Savin

Step 1: Reformulation of the condition

The table is a cyclic Latin square, so the entry in row $i$ and column $j$ equals $j-i+1 \pmod n$ in the set ${1,2,\dots,n}$.

A choice of $n$ cells with distinct rows and columns corresponds to a permutation $\sigma$ of ${1,\dots,n}$, where from row $i$ we take column $\sigma(i)$. The chosen entry is then

$a_i \equiv \sigma(i) - i + 1 \pmod n.$

Thus the problem is equivalent to finding a permutation $\sigma$ such that the values $a_i$ are all distinct, i.e. the map

$f(i) = \sigma(i) - i \pmod n$

is also a permutation of $\mathbb{Z}_n$ up to relabeling. Equivalently, the chosen entries must form a permutation of ${1,\dots,n}$.

So we are looking for a way to select one entry in each row and column such that the selected symbols also run through all $1,\dots,n$ exactly once.

Step 2: Source of error in the previous solution

The previous solution attempted a modular-sum obstruction for even $n$ and a diagonal-type construction for odd $n$. The obstruction step relied on an unjustified global congruence relating selected entries to the full set ${1,\dots,n}$. That reasoning is invalid because the chosen entries do not form a fixed residue class pattern across rows.

The construction for odd $n$ also failed because it did not directly guarantee that the selected values cover all symbols.

A correct approach must explicitly construct a valid selection and separately show impossibility when $n$ is even.

Step 3: Construction for odd $n$

Assume $n$ is odd. Define a choice of columns by

$\sigma(i) \equiv i+1 \pmod n,$

where indices are taken modulo $n$ with values in ${1,\dots,n}$.

This is a permutation of columns because it is a cyclic shift.

The selected entry in row $i$ is

$a_i = \sigma(i) - i + 1 \equiv (i+1) - i + 1 \equiv 2i+1 \pmod n.$

So the set of chosen numbers is

${2i+1 \pmod n : i=1,\dots,n}.$

When $n$ is odd, $\gcd(2,n)=1$, so multiplication by $2$ is a bijection on $\mathbb{Z}_n$. Therefore the map $i \mapsto 2i+1$ is a permutation of $\mathbb{Z}_n$, and every residue class modulo $n$ appears exactly once among the $a_i$.

After relabeling residues $0,1,\dots,n-1$ as $1,\dots,n$, this means the selected entries are exactly the numbers $1,2,\dots,n$, all distinct.

Thus a valid selection exists for every odd $n$.

Step 4: Impossibility for even $n$

Assume $n$ is even and suppose a valid selection exists.

As above, the selection corresponds to a permutation $\sigma$, and the selected values are

$a_i \equiv \sigma(i) - i + 1 \pmod n.$

Rewrite in $\mathbb{Z}_n$ by shifting by $1$, which does not affect bijectivity. Define

$b_i \equiv \sigma(i) - i \pmod n.$

Then ${b_i}$ must be a permutation of $\mathbb{Z}_n$.

Summing over all $i$,

$\sum_{i=1}^n b_i \equiv \sum_{i=1}^n \sigma(i) - \sum_{i=1}^n i \pmod n.$

Since $\sigma$ is a permutation,

$\sum_{i=1}^n \sigma(i) = \sum_{i=1}^n i,$

$\sum_{i=1}^n b_i \equiv 0 \pmod n.$

However, if ${b_i}$ is a permutation of $\mathbb{Z}_n$, then its sum is

$0+1+\cdots+(n-1) = \frac{n(n-1)}{2} \equiv \frac{n}{2} \pmod n$

because $n$ is even.

This gives

$0 \equiv \frac{n}{2} \pmod n,$

which is impossible since $\frac{n}{2}$ is not divisible by $n$.

Therefore no such selection exists when $n$ is even.

Step 5: Conclusion

A valid selection exists for every odd $n>1$ via the cyclic shift construction, and no selection is possible for even $n$ due to an unavoidable contradiction in the sum invariant of the induced difference permutation.

The set of all admissible values is

$\boxed{\text{all odd natural numbers } n>1}.$