## Task 3A - 281233A

Determine all natural numbers $n \geq 3$ for which it is possible to specify a natural number $a_{i}$ for each $i=1,2, \ldots, n$ such that the following conditions are satisfied:

(1) For all $i$ with $1 \leq i \leq n$, $0 \leq a_{i} \leq \frac{1}{2}(n-1) \cdot n$.

(2) No two of the differences $a_{j}-a_{i}$, which can be formed for all $i, j$ with $1 \leq i \leq n, 1 \leq j \leq n$ and $i \neq j$, are equal.
I. For $n=3$, the conditions are, for example, satisfied by $a_{1}=0, a_{2}=1, a_{3}=3$ with the differences $\{-1,-3,-1,-2,3,2\}$.

II. For $n=4$, the conditions are, for example, satisfied by $a_{1}=0, a_{2}=1, a_{3}=4, a_{4}=6$ with the differences $\{-1,-4,-6,1,-3,-5,4,3,-2,6,5,2\}$.

III. Suppose now, for some $n \geq 5$, (1) and (2) are satisfied by natural numbers $a_{1}, \ldots, a_{n}$. Then it follows:

(3) No two of the numbers $a_{1}, \ldots, a_{n}$ are equal.

Proof:

If $a_{j}=a_{k}(j \neq k)$, then with an $i$ different from $j$ and $k$, it would follow that $a_{j}-a_{i}=a_{k}-a_{i}$, which contradicts (2).

Without loss of generality, due to (1), it can be assumed:

(4) It holds that $0 \leq a_{1}<a_{2}<\ldots<a_{n-1}<a_{n} \leq \frac{1}{2}(n-1) n$.

Further, it holds:

(5) The differences $a_{j}-a_{i}$, formed for all $i, j$ with $1 \leq i<j \leq n$, are the numbers $1,2, \ldots, \frac{1}{2}(n-1) n$ in some order, each exactly once.

Proof:

According to (4), $0<a_{j}-a_{i} \leq \frac{1}{2}(n-1) n$ for each of these differences. According to (2), they are pairwise distinct, so their number is equal to the number of pairs $(i, j)$ with $1 \leq i<j \leq n$. This number is $\frac{1}{2}(n-1) n$, hence (5) must hold.

In particular, it holds:

(6) The differences $d_{i}=a_{i+1}-a_{i}$, formed for all $i=1, \ldots, n-1$, are the numbers $1,2, \ldots, n-1$ in some order, each exactly once.

Proof:

According to (4), the sum of these differences is

$$
d_{1}+\ldots+d_{n-1}=a_{n}-a_{i} \leq \frac{1}{2}(n-1) n
$$

According to (2), they are pairwise distinct natural numbers, and according to (4), they are positive.

However, the sum of the numbers $1,2, \ldots, n-1$ is known to be $\frac{1}{2}(n-1) n$, so only the possibility (6) remains.

Now we obtain: According to (6), there is exactly one index $p$ among the indices $1, \ldots, n-1$ with $d_{p}=1$. If an index $r(1 \leq r \leq n-1)$ is an upper or lower neighbor of $p$, then $d_{r}=n-1$ must hold; for if for two adjacent indices $i, i+1$ one of the two numbers $d_{i}, d_{i+1}$ were equal to 1 and the other less than $n-1$, then

$$
a_{i+2}-a_{i}=d_{i+1}+d_{i}<n
$$

which would contradict (2) due to (6).

Thus, $p$ must be one of the two indices $1, n-1$ with only one neighbor, and for this neighbor index $r$ with $d_{r}=n-1$; i.e., one of the two cases A, B must hold:

A: It holds $d_{1}=1, d_{2}=n-1$ B: It holds $d_{n-1}=1, d_{n-2}=n-1$.

Similarly, we obtain: There is exactly one index $q$ with $d_{q}=2$. If an index $s$ is an upper or lower neighbor of $q$, then $d_{s}$ must be one of the numbers $n-2, n-1$. Because $n \geq 5$, these two numbers are different from 1 and 2.

Thus, if $q$ has two neighbors, one of them must be the index $r$ already fixed in cases A, B, and for the other neighbor $s$, $d_{s}=n-2$ must hold.

If $q$ has only one neighbor $s$ (i.e., $q=n-1$ in case A or $q=1$ in case B), then because $n \geq 5$, this neighbor is not the index $r$ fixed in cases A, B; thus, only $d_{s}=n-2$ can hold. That is, in each case A or B, one of the subcases A1, A2 or B1, B2 must hold:

A1: It holds $d_{1}=1, d_{2}=n-1, d_{3}=2, d_{4}=n-2$

A2: It holds $d_{1}=1, d_{2}=n-1, d_{n-1}=2, d_{n-2}=n-2$

B1: It holds $d_{n-1}=1, d_{n-2}=n-1, d_{n-3}=2, d_{n-4}=n-2$.

B2: It holds $d_{n-1}=1, d_{n-2}=n-1, d_{1}=2, d_{2}=n-2$.

Thus, in each case, there are four indices of the form $u, u+1, v, v+1$ with $u \neq v$, for which $d_{u}+d_{u+1}=n, d_{v}+d_{v+1}=n$ and thus $a_{u+2}-a_{u}=a_{v+2}-a_{v}$ holds. This contradicts (6).

The assumption that (1) and (2) are satisfiable for some $n \geq 5$ has thus led to a contradiction in each case.

With I., II., III., it is proven: The conditions of the problem are satisfied exactly by the two numbers $n=3$ and $n=4$.

## Adapted from $[5]$