Let $K$ and $N>K$ be fixed positive integers. Let $n$ be a positive integer and let $a_{1}, a_{2}, \ldots, a_{n}$ be distinct integers. Suppose that whenever $m_{1}, m_{2}, \ldots, m_{n}$ are integers, not all equal to 0, such that $\left|m_{i}\right| \leqslant K$ for each $i$, then the sum

$$
\sum_{i=1}^{n} m_{i} a_{i}
$$

is not divisible by $N$. What is the largest possible value of $n$?

## Proposed by North Macedonia
The answer is $n=\left\lfloor\log _{K+1} N\right\rfloor$.
Note first that for $n \leqslant\left\lfloor\log _{K+1} N\right\rfloor$, taking $a_{i}=(K+1)^{i-1}$ works. Indeed let $r$ be maximal such that $m_{r} \neq 0$. Then on the one hand we have

$$
\left|\sum_{i=1}^{n} m_{i} a_{i}\right| \leqslant \sum_{i=1}^{n} K(K+1)^{i-1}=(K+1)^{n}-1
$$

So the sum is indeed not divisible by $N$.
Assume now that $n \geqslant\left\lfloor\log _{K+1} N\right\rfloor$ and look at all $n$-tuples of the form $\left(t_{1}, \ldots, t_{n}\right)$ where each $t_{i}$ is a non-negative integer with $t_{i} \leqslant K$. There are $(K+1)^{n}>N$ such tuples so there are two of them, say $\left(t_{1}, \ldots, t_{n}\right)$ and $\left(t_{1}^{\prime}, \ldots, t_{n}^{\prime}\right)$ such that

$$
\sum_{i=1}^{n} t_{i} a_{i} \equiv \sum_{i=1}^{n} t_{i}^{\prime} a_{i} \bmod N
$$

Now taking $m_{i}=t_{i}-t_{i}^{\prime}$ for each $i$ satisfies the requirements on the $m_{i}$ 's but $N$ divides the sum

$$
\sum_{i=1}^{n} m_{i} a_{i}
$$

a contradiction.