For which integers $N$ it is possible to write real numbers into the cells of a square of size $N \times N$ so that among the sums of each pair of adjacent cells there are all integers from $1$ to $2(N-1)N$ (each integer once)? Maxim Didin
Problem
Source: Tournament of Towns, Junior A-Level Paper, Spring 2020 , p4
Tags: combinatorics, square grid, table
10.06.2020 15:54
Hint: Suppose that we have a completion like in the statement (and call it good). Then color the squares of the table white and black such that no 2 adjacent cells share the same color. Then for some $k$ add $k$ in every white cell and $-k$ in every black cell. The new completion is also good. Hence let $a$ be one of the elements in the table and let $k=-\{a\}$ and color the cell $a$ is in white. Hence the new number in $a$'s cell is an integer so therefore every other number is an integer. So a good completion with numbers from $\mathbb{R}$ exists if and only if there is a good completion with numbers from $\mathbb{N}$. So the new statement is: For which integers $N$ it is possible to write integers into the cells of a square of size $N \times N$ so that among the sums of each pair of adjacent cells there are all integers from $1$ to $2(N-1)N$ (each integer once)?
08.04.2021 23:11
$\color{blue} \textbf{\text{Answer.}}$ $\boxed{\text{Every } N\geq 2.}$ $\color{blue} \textbf{\text{Solution.}}$ Obviously, $N=1$ does not work. We claim that every $N\geq 2$ works, by induction. Base case $N=2$. Consider the following construction. [asy][asy] size(2cm); for (int i=0; i<=1; ++i) { draw(shift(i,1)*unitsquare); } for (int i=0; i<=1; ++i) { draw(shift(i,0)*unitsquare); } label("$3/2$", (1/2,1/2)); label("$1/2$", (1/2,3/2)); label("$1/2$", (3/2,3/2)); label("$5/2$", (3/2,1/2)); [/asy][/asy] Suppose that for some $N$ (here we consider odd $N$), we $N \times N$ satisfying the conditions with the last column consists of $a,a+1,a+2,\ldots,a+N-2,a+N-1$ from the top to the bottom and last row consists of $a,a,a+2,a+2,\ldots,a+N-3,a+N-3,a+N-1$ from the left to the right, where $a=\frac{2N^2-4N+3}{2}$. Now, we claim that $N+1$th row consists of $b,b+1,b+2,\ldots,b+N-1,b+N$ from the left to the right and $N+1$th column consists of $b-1,b+1,b+1,\ldots,b+N-2,b+N-2,b+N$ from the top to the bottom, works, where $b=\frac{2N^2+1}{2}$. Obviously, we cover the sums $a+b-1$ to $a+b+2N-2$ and now $2b$ to $2b+2N-1$. We have infact equalities, $$a+b-1=\frac{2N^2-4N+3}{2}+\frac{2N^2+1}{2}-1=2(N-1)N+1$$$$a+b+2N-2=2(N-1)N+1+2N-1=2N^2$$$$2b=2\cdot \frac{2N^2+1}{2}=2N^2+1$$$$2b+2N-1=2N^2+1+2N-1=2N(N+1).$$Thus, we cover by this induction step $2(N-1)N+1$ to $2N(N+1)$ and by the inductive hypothesis, we already covered $1$ to $2(N-1)N$ inside $N\times N$, hence we covered sums $1$ to $2N(N+1)$ in $(N+1)\times (N+1)$. [asy][asy] size(6cm); for (int i=0; i<=4; ++i) { draw(shift(i,0)*unitsquare); } for (int i=0; i<=4; ++i) { draw(shift(4,i)*unitsquare); } pen smaller=fontsize(6pt); for (int i=0; i<=3; ++i) { draw(shift(i,1)*unitsquare); } for (int i=1; i<=4; ++i) { draw(shift(3,i)*unitsquare); } label("$a+N-1$", (7/2,3/2),smaller); label("$\ldots$", (5/2,3/2)); label("$\vdots$", (7/2,5/2)); label("$\ldots$", (5/2,1/2)); label("$b+N$", (9/2,1/2)); label("$\vdots$", (9/2,5/2)); label("$b+N-2$", (9/2,3/2),smaller); label("$b+N-1$", (7/2,1/2),smaller); label("$b-1$", (9/2,9/2)); label("$b+1$", (9/2,7/2)); label("$b$", (1/2,1/2)); label("$b+1$", (3/2,1/2)); label("$a$", (3/2,3/2)); label("$a$", (1/2,3/2)); label("$a$", (7/2,9/2)); label("$a+1$", (7/2,7/2)); [/asy][/asy] If $N$ is even, then we have a previous odd case without the first row and the first column, i.e. our last row consists of $a,a+2,a+2,\ldots, a+N-3,a+N-3,a+N-1$ from the left to the right and last column consists of $a+1,a+2,\ldots,a+N-2,a+N-1$, where $a=\frac{2N^2-4N+1}{2}$. Now, we claim that $N+1$th row consists of $b+1,b+2,\ldots,b+N-1,b+N$ from the left to the right and $N+1$th column consists of $b+1,b+1,\ldots,b+N-2,b+N-2,b+N$ from the top to the bottom, works, where $b=\frac{2N^2-1}{2}$. Obviously, we cover the sums $a+b+1$ to $a+b+2N-2$ and now $2b+2$ to $2b+2N-1$. We have infact equalities, $$a+b+1=\frac{2N^2-4N+1}{2}+\frac{2N^2-1}{2}+1=2(N-1)N+1$$$$a+b+2N-2=2(N-1)N+1+2N-1=2N^2$$$$2b+2=2\cdot \frac{2N^2-1}{2}+2=2N^2+1$$$$2b+2N-1=2N^2+1+2N-1=2N(N+1).$$Thus, we cover by this induction step $2(N-1)N+1$ to $2N(N+1)$ and by the inductive hypothesis, we already covered $1$ to $2(N-1)N$ inside $N\times N$, hence we covered sums $1$ to $2N(N+1)$ in $(N+1)\times (N+1)$. We are done. Construction example shown for $n=4$. [asy][asy] size(4cm); for (int i=0; i<=3; ++i) { draw(shift(i,3)*unitsquare); } for (int i=0; i<=3; ++i) { draw(shift(i,2)*unitsquare); } for (int i=0; i<=3; ++i) { draw(shift(i,1)*unitsquare); } for (int i=0; i<=3; ++i) { draw(shift(i,0)*unitsquare); } label("$19/2$", (1/2,1/2)); label("$3/2$", (1/2,5/2)); label("$9/2$", (1/2,3/2)); label("$1/2$", (1/2,7/2)); label("$21/2$", (3/2,1/2)); label("$5/2$", (3/2,5/2)); label("$9/2$", (3/2,3/2)); label("$1/2$", (3/2,7/2)); label("$23/2$", (5/2,1/2)); label("$11/2$", (5/2,5/2)); label("$13/2$", (5/2,3/2)); label("$9/2$", (5/2,7/2)); label("$25/2$", (7/2,1/2)); label("$21/2$", (7/2,5/2)); label("$21/2$", (7/2,3/2)); label("$17/2$", (7/2,7/2)); [/asy][/asy]