One needs to ffll the cells of an $n\times n$ table ($n > 1$) with distinct integers from $1$ to $n^2$ so that every two consecutive integers are placed in cells that share a side, while every two integers with the same remainder if divided by $n$ are placed in distinct rows and distinct columns. For which $n$ is this possible? (Alexandr Gribalko)
Problem
Source: Tournament of Towns, Junior A-Level , Spring 2019 p5
Tags: square grid, numbers in a table, table, combinatorics
Unit10
19.02.2021 20:50
Can someone solve this ?
math90
20.02.2021 00:24
Answer: All even numbers. Here is an example for $n=6$ which demonstrates the pattern for even numbers. $$\begin{array}{|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6\\ \hline 36 & 11 & 10 & 9 & 8 & 7\\ \hline 35 & 12 & 13 & 14 & 15 & 16\\ \hline 34 & 21 & 20 & 19 & 18 & 17\\ \hline 33 & 22 & 23 & 24 & 25 & 26\\ \hline 32 & 31 & 30 & 29 & 28 & 27 \\\hline \end{array}$$ Now assume the problem is true for some $n$. For a number in cell $(i,j)$ in a table, let its weight be $i+j$. Since $1,n+1,\dots,n(n-1)+1$ lie in different rows and different columns, the sum of their weights is twice the sum of all numbers from $1$ to $n$. Similarly, the sum of weights of all numbers in $2,n+2,\dots,n(n-1)+2$ is twice the sum of all numbers from $1$ to $n$. But these numbers are successive to the numbers in the first list, so the sum is obtained from the former sum by adding $n$ numbers which are $\pm 1$. If $n$ is odd, the sum must change.
Kamran011
20.02.2021 12:52
Nice problem
evens
$$\begin{array}{|c|c|c|c|c|c|}
\hline 1 & 2 & 3 & 4 & 5 & 6\\
\hline 36 & 27 & 26 & 17 & 16 & 7\\
\hline 35 & 28 & 25 & 18 & 15 & 8\\
\hline 34 & 29 & 24 & 19 & 14 & 9\\
\hline 33 & 30 & 23 & 20 & 13 & 10\\
\hline 32 & 31 & 22 & 21 & 12 & 11
\\\hline \end{array}$$, the same construction is true for any even $n$
Assume ftsc we put these numbers in required form into a $n\times n$ board, where $n$ is odd. Observe that for arbitrary residue $k$, the sum of the coordinates of the cells containing a number $k\pmod n$ is twice the sum $1+\dots+n$, in particular it is even. Color the board as in a chessboard so that the left-top corner is black. The quick fact is that the sum of coordinates of black and white cells are even and odd respectively, which yields : $\#$(numbers $k\pmod n$ in white cells) is even. Consider $$1, n+1, \cdots, (n-1)n+1$$and $$2, n+2, \cdots, (n-1)n+2$$, the relation between them is obvious, it tells us that $\#$(numbers $1\pmod n$ in white cells) which is even, equals $\#$(numbers $2\pmod n$ in black cells) which is odd, absurd.