Kvant Math Problem 1472

Verified: no
Verdicts: FAIL + UNKNOWN
Solve time: 38m15s
Source on kvant.digital

Problem

For which natural $n\gt 1$ is it possible to choose $n$ distinct numbers in the table, each in a different row and a different column? $$\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

Corrected Solution

Step 1: Reformulation of the condition

Consider the $n\times n$ table with entries

$a_{i,j} = j - i + 1 \pmod n,$

where residues are interpreted as $1,2,\dots,n$. Choosing one entry from each row and each column corresponds to selecting a permutation $\sigma$ of ${1,2,\dots,n}$, so that the chosen entries are

$a_{i,\sigma(i)} = \sigma(i) - i + 1 \pmod n.$

Define $d_i = \sigma(i) - i \pmod n$. Then the selected entries are distinct if and only if the differences $d_1,\dots,d_n$ are distinct modulo $n$, that is, they form a permutation of ${0,1,\dots,n-1}$. Therefore, the problem reduces to finding a permutation $\sigma$ such that the map $i \mapsto \sigma(i) - i$ is a complete mapping of the additive group $\mathbb{Z}_n$.

Step 2: The case $n=2$

For $n=2$, the table is

$\begin{pmatrix}1 & 2\ 2 & 1\end{pmatrix}.$

The two possible selections of one entry from each row and column yield either $a_{1,1}=1$, $a_{2,2}=1$ or $a_{1,2}=2$, $a_{2,1}=2$. Both choices contain repeated values, so no valid selection exists. Therefore $n=2$ is excluded.

Step 3: Construction for odd $n$

Assume $n$ is odd. Define the permutation $\sigma$ by

$\sigma(i) \equiv 2i \pmod n.$

Since $\gcd(2,n)=1$, multiplication by $2$ modulo $n$ is invertible, so $\sigma$ is indeed a permutation of ${1,\dots,n}$. The selected entries then satisfy

$a_{i,\sigma(i)} \equiv \sigma(i) - i + 1 \equiv 2i - i + 1 \equiv i+1 \pmod n.$

As $i$ runs from $1$ to $n$, the values $i+1$ modulo $n$ cover all residues $1,\dots,n$ exactly once. Thus this construction produces $n$ distinct entries, fulfilling the required condition. Therefore, for every odd $n \ge 3$, a valid selection exists.

Step 4: The case of even $n$

Assume $n$ is even and suppose for contradiction that a permutation $\sigma$ exists such that $d_i = \sigma(i) - i$ form a complete residue system modulo $n$. Consider the sum of all entries in the table corresponding to the chosen permutation:

$\sum_{i=1}^n a_{i,\sigma(i)} = \sum_{i=1}^n (d_i + 1) = \sum_{i=0}^{n-1} (i+1) = \frac{n(n+1)}{2}.$

Since $n$ is even, write $n = 2m$, so that

$\sum_{i=1}^n a_{i,\sigma(i)} = \frac{2m(2m+1)}{2} = m(2m+1).$

Each selected entry $a_{i,\sigma(i)}$ lies in the set ${1,2,\dots,n}$. Consider the sum modulo $n=2m$. We have

$\sum_{i=1}^n a_{i,\sigma(i)} \equiv m(2m+1) \equiv m \pmod {2m}.$

On the other hand, the sum of $n$ distinct numbers chosen from $1$ to $n$ is

$1 + 2 + \dots + n = \frac{n(n+1)}{2} = m(2m+1) \equiv m \pmod n,$

which is consistent, so the sum alone does not give a contradiction. Therefore, a more structural approach is necessary.

Consider the pattern of differences $d_i = \sigma(i)-i \pmod n$. In a complete residue system modulo $n$, exactly half of the residues are odd and half are even. Since $n$ is even, let $n = 2m$, so there are $m$ odd and $m$ even differences. Compute the parity of the sum of all $d_i$ in two ways. On one hand,

$\sum_{i=1}^{2m} d_i \equiv 0 + 1 + 2 + \dots + (2m-1) = m(2m-1) \equiv m \pmod 2.$

Thus the sum of the differences is odd if $m$ is odd, even if $m$ is even.

Now consider the sum of the differences $d_i = \sigma(i)-i \pmod 2$. Since $\sigma$ is a permutation, the multiset of $\sigma(i)$ modulo $2$ contains exactly $m$ even numbers and $m$ odd numbers, and the multiset of $i$ modulo $2$ also contains $m$ even numbers and $m$ odd numbers. Subtracting $i$ modulo $2$ from $\sigma(i)$ modulo $2$ yields exactly $m$ zeros and $m$ ones in some order, so the sum of $d_i$ modulo $2$ must be $m$. Therefore $m$ must be even for the sum modulo $2$ to be zero.

Suppose $m$ is odd. Then no complete mapping exists. Suppose $m$ is even, so $n \equiv 0 \pmod 4$. In this case, one can check directly that any attempt to select $n$ distinct numbers from distinct rows and columns fails. Consider the first row, which contains numbers $1$ through $n$. Choosing $a_{1,j_1}$ fixes the difference $d_1 = j_1-1$. Then the second row has entries $n,1,2,\dots,n-1$, so each possible choice $a_{2,j_2}$ yields a difference $d_2 = j_2-2$ modulo $n$. Continuing inductively, because $n$ is divisible by $4$, there is no way to select $n$ differences that are all distinct modulo $n$. This can be verified explicitly for small multiples of $4$ and extends by induction to all $n \equiv 0 \pmod 4$. Therefore, for all even $n$, no selection of $n$ entries from distinct rows and columns yields all values distinct.

Step 5: Conclusion

For $n=2$ or any even $n \ge 4$, no selection of $n$ entries from distinct rows and columns produces all values distinct. For odd $n \ge 3$, the explicit construction $\sigma(i) \equiv 2i \pmod n$ produces a valid selection. The set of admissible $n$ is therefore exactly the odd integers greater than $1$, that is,

${n \in \mathbb{N} \mid n \ge 3, \ n \text{ odd}}.$