Sum of pairwise products divisible by $n$

164 Views Asked by At

We write three rows of numbers on top of each other, each row consisting of a permutation of $1,2,\dots,n$. It turns out that for each column, the sum of the three pairwise products is divisible by $n$. For which $n$ is this possible?

$n=1$ is obviously possible, and $n=3$ is possible if all rows are $123$. On the other hand, $n=2$ is impossible by trial and error. Taking all rows to be $12\dots n$ doesn't work for any $n>3$.

As written in the comments, for odd $n$ it is possible to have two rows of $1,2,\dots,n$ and one row of $(n-1)/2,n-1,(n-3)/2,n-2,\dots,1,(n+1)/2,n$. Note that if a column consists of two $x$'s and one $y$, the sum of the pairwise products is $x^2+2xy=x(x+2y)$. It then suffices to note that for each column, $x+2y$ is divisible by $n$.

1

There are 1 best solutions below

2
On BEST ANSWER

Even $n$ is impossible:

Consider each column $a,b,c$. If all three are odd, then $ab+ac+bc$ is odd. If two of $a,b,c$ are odd, (say $a=2k$), then $2kb+2kc+bc$ is again odd.

Hence, if $n$ is even, then every column must contain at least two even numbers. But then we must write at least $\frac{2}{3}(3n)=2n$ even numbers. This is impossible, since there are only $\frac{n}{2}$ even numbers in each row, so $\frac{3}{2}n$ even numbers total.


Odd $n$ is possible:

Let the first two rows be $1,2,\ldots, n$. Specify the third row (below $a,a$) to be that $b$ which satisfies $2b+a\equiv 0\pmod{n}$. This has a unique solution for each odd $n$. Further, if $2b+a\equiv 0\equiv 2b+a'$, then $a=a'$, so the entries in the third row are indeed a permutation of $1,2,\ldots, n$.