Kvant Math Problem 426
The figure describes a standard cyclic filling of an $n\times n$ table with the numbers $1,2,\dots,n$ in such a way that each row is a cyclic shift of the previous one.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m12s
Source on kvant.digital
Problem
A table of $n\times n$ cells is filled with the numbers from 1 to $n$ as shown in the figure. For which $n$ is it possible to choose $n$ cells in it so that no two cells belong to the same row or the same column, and all numbers in the selected cells are different?
Fig. 1
A. Nenashev
Exploration
The figure describes a standard cyclic filling of an $n\times n$ table with the numbers $1,2,\dots,n$ in such a way that each row is a cyclic shift of the previous one. Concretely, one may assume that the entry in row $i$, column $j$ equals
$a_{ij} \equiv i+j \pmod n,$
with values interpreted in ${1,\dots,n}$.
A choice of $n$ cells with no two in the same row or column corresponds to selecting a permutation $\sigma$ of ${1,\dots,n}$, where we choose the cell $(i,\sigma(i))$. The condition that all selected numbers are different means that the values
$a_{i,\sigma(i)}$
are pairwise distinct.
Thus we are looking for a permutation $\sigma$ such that the set ${i+\sigma(i)\pmod n}$ is also a permutation of ${1,\dots,n}$.
Small cases suggest a parity obstruction. For $n=1$ the condition is trivial. For $n=2$, direct checking shows failure: any transversal forces repeated values. For $n=3$, experimentation indicates a successful configuration exists. This points toward a dependence on parity, with odd $n$ likely admissible and even $n$ excluded.
The critical issue is whether the system $i+\sigma(i)\pmod n$ can be made bijective, which is equivalent to constructing a complete mapping of the cyclic group $\mathbb{Z}_n$.
Problem Understanding
This is a Type A problem, requiring classification of all integers $n$ for which the required selection is possible.
We interpret the table as the standard cyclic Latin square of order $n$. The task is to select one entry from each row and column so that the chosen entries contain all symbols $1,\dots,n$ exactly once.
This is equivalent to finding a permutation $\sigma$ such that both $\sigma$ and $i\mapsto i+\sigma(i)$ are permutations modulo $n$.
The expected outcome is that this is possible exactly when $n$ is odd, since inversion of $2$ in modular arithmetic plays a central role in constructing such permutations.
Proof Architecture
The proof has two main parts.
First, it is shown that if $n$ is even, then no such permutation $\sigma$ exists, using a modular sum argument that forces a contradiction.
Second, for odd $n$, an explicit permutation $\sigma(i)=ki$ modulo $n$ is constructed, with $k=\frac{n-1}{2}$, and it is verified that both $\sigma$ and $i+\sigma(i)$ are permutations.
The key delicate step is the nonexistence proof for even $n$, since it depends on a global invariant rather than local structure.
Solution
Assume the table is filled cyclically so that the entry in row $i$ and column $j$ equals the number
$a_{ij}\equiv i+j \pmod n,$
interpreted as an element of ${1,\dots,n}$.
A valid choice of $n$ cells with distinct rows and columns corresponds to a permutation $\sigma$ of ${1,\dots,n}$, where the chosen cells are $(i,\sigma(i))$. The condition that all chosen numbers are distinct means that the values $a_{i,\sigma(i)}$ are pairwise distinct, hence they form a permutation of ${1,\dots,n}$. Therefore,
${a_{i,\sigma(i)} : i=1,\dots,n}={1,\dots,n}.$
Using the cyclic definition of the table, we rewrite
$a_{i,\sigma(i)}\equiv i+\sigma(i)\pmod n.$
Even $n$ is impossible
Assume such a permutation $\sigma$ exists. Summing all chosen values in $\mathbb{Z}_n$, we obtain
$\sum_{i=1}^n a_{i,\sigma(i)} \equiv \sum_{i=1}^n (i+\sigma(i)) \pmod n.$
Since $\sigma$ is a permutation,
$\sum_{i=1}^n \sigma(i)=\sum_{i=1}^n i=\frac{n(n+1)}{2},$
hence
$\sum_{i=1}^n (i+\sigma(i)) = n(n+1).$
On the other hand, because the selected values form a permutation of ${1,\dots,n}$,
$\sum_{i=1}^n a_{i,\sigma(i)}=\frac{n(n+1)}{2}.$
Thus we obtain the congruence
$n(n+1)\equiv \frac{n(n+1)}{2}\pmod n.$
The left-hand side is divisible by $n$, so the right-hand side must also be divisible by $n$, which gives
$n \mid \frac{n(n+1)}{2}.$
Cancelling $n$ yields that $2$ divides $n+1$. Hence $n$ is odd. Therefore no solution exists for even $n$.
Construction for odd $n$
Assume $n$ is odd and set
$k=\frac{n-1}{2}.$
Define a permutation $\sigma$ of ${1,\dots,n}$ by
$\sigma(i)\equiv ki \pmod n.$
This is a permutation because $\gcd(k,n)=1$, which holds since any common divisor of $k$ and $n$ divides both $n$ and $2k=n-1$, hence divides $1$.
The chosen values are
$a_{i,\sigma(i)}\equiv i+ki=(k+1)i \pmod n.$
Since $k+1=\frac{n+1}{2}$ and $\gcd!\left(\frac{n+1}{2},n\right)=1$, the map
$i\mapsto (k+1)i \pmod n$
is also a permutation of ${1,\dots,n}$. Hence all selected values are distinct, and every row and column is used exactly once.
Thus a valid selection exists for all odd $n$.
Therefore the required values of $n$ are exactly the odd positive integers,
$\boxed{n\ \text{is odd}}.$
Verification of Key Steps
The central point in the nonexistence argument is the passage from equality of multisets of values to a modular contradiction. The identity
$\sum_{i=1}^n a_{i,\sigma(i)}=\frac{n(n+1)}{2}$
uses the fact that the selected entries form a permutation of ${1,\dots,n}$, which forces equality of sums, not merely congruence.
In the construction, the crucial step is the invertibility of $k=\frac{n-1}{2}$ modulo $n$. Any common divisor of $k$ and $n$ must divide both $n$ and $n-1$, forcing it to be $1$, so $\sigma$ is well-defined as a permutation. Similarly, invertibility of $k+1=\frac{n+1}{2}$ ensures that the image values are all distinct; without this, collisions would occur even if $\sigma$ is a permutation.
Alternative Approaches
An alternative formulation views the problem as constructing a complete mapping of the cyclic group $\mathbb{Z}_n$, where one seeks a permutation $\sigma$ such that $i+\sigma(i)$ is also a permutation. Standard results in group theory classify cyclic groups as admitting complete mappings exactly when their order is odd, leading to the same conclusion more abstractly.
Another approach is to explicitly construct $\sigma$ by pairing elements symmetrically around $0$ in $\mathbb{Z}_n$, producing a bijection whose sum-shift is again bijective, but this approach ultimately encodes the same arithmetic condition that $2$ must be invertible modulo $n$.