Serbian Mathematical Olympiad

Solution:

We denote by $F_{i}$ the Fibonacci numbers: $F_{1}=F_{2}=1, F_{i+1}=F_{i}+F_{i-1}$. Let us consider the set $A=\{a_{1}, a_{2}, \ldots, a_{k+1}\}$ with $n=F_{k+2}+3$, where
$$a_{i}=(-1)^{k-1-i} F_{i+1} \text{ for } i=1,2, \ldots, k-1, \quad a_{k}=F_{k}+1 \quad \text{and} \quad a_{k+1}=F_{k}+2$$
In the case of even $k$ we see that $a_{i}=a_{i+1}+a_{i+2}(1 \leqslant i \leqslant k-3), a_{k-2} \equiv a_{k}+a_{k+1}$ $(\bmod n), a_{k-1}=a_{k+1}+a_{2}, a_{k}=a_{k-1}+a_{1}$ and $a_{k+1}=a_{k}+a_{1}$, so the set $A$ satisfies the first condition of the problem. This condition is checked similarly for odd $k$.

Let us prove by induction on $k$ (the base case $k=3$ is checked directly) that the second condition is also satisfied, i.e., that there does not exist a subset $B \subsetneq A$ such that $n \mid \sum_{b \in B} b$. Since the sum of the elements of the set $A$ equals zero, we may assume without loss of generality (by replacing $B$ with $A \backslash B$ if necessary) that $B$ contains at most one of the elements $F_{k}, F_{k}+1, F_{k}+2$. Then
$1-F_{k}=-\left(F_{k-1}+F_{k-3}+\cdots\right) \leqslant \sum_{b \in B} b \leqslant\left(F_{k}+2\right)+F_{k-2}+F_{k-4}+\cdots=F_{k+1}+1$,
so it must be that $\sum_{b \in B} b=0$. Based on the induction hypothesis for $k-1$, the set $B$ cannot be a subset of the set $\{a_{1}, a_{2}, \ldots, a_{k-2}\}$, i.e., it must be that $a_{k-1}=F_{k} \in B$. However, then $\sum_{b \in B} b \geqslant F_{k}-F_{k-1}-F_{k-3}-\cdots=1$, which is a contradiction. The proof is complete.

Therefore, $n_{k} \leqslant F_{k+2}+3<\phi^{k-3}\left(F_{5}+3\right)<\phi^{k+2}<\left(\frac{13}{8}\right)^{k+2}$, where $\phi=\frac{1+\sqrt{5}}{2}$.