Valentin: you use a nice $-$ sign Claim: $n=9$. When taking the $\epsilon_i$ from the set $\{0,1\}$ only, all numbers that are reached by this have to be different $\mod n^3$ since otherwise subtracting them gives a number that can be written with $\epsilon_i \in \{-1,0,1\}$ and is divisible by $n^3$. Thus $2^n \leq n^3$, which is just true for $2 \leq n \leq 9$. But now we can take $x_1=1 , x_2 = 2 , x_3=4 , ... , x_9=2^8=256$ and it's easy to see that the moduli of the possible sums are not $0$ (use that the $2$-adic valuation is not $\infty$ for all sums that are allowed) and smaller than $9^3>511=2^8+2^7+...+4+2+1$, so not divisible by $9^3$.

Because$2^{10} >10^3$

I don't think I understand this problem. If we take $x_i=i$, then the maximum value of $|\varepsilon_1x_1+\dots+\varepsilon_nx_n|=1+2+\dots+n=n(n+1)/2<n^3$, for $n\geq 2$. Then $n^3\nmid \varepsilon_1 x_1 + \varepsilon_2 x_2 + \cdots + \varepsilon_n x_n$. Thus shouldn't all $n$ work? I am surely misunderstanding the problem statement. Please help

@above I think that you missed the case that, if we take $\varepsilon_3, \varepsilon_4,\cdots,\varepsilon_n=0$ and $\varepsilon_1=-1, \varepsilon_2=-1, \varepsilon_3=1$, then the sum $\varepsilon_1 x_1 + \varepsilon_2 x_2 + \cdots + \varepsilon_n x_n=0$, which is divisible by $n^3$.

Severus wrote: I don't think I understand this problem. If we take $x_i=i$, then the maximum value of $|\varepsilon_1x_1+\dots+\varepsilon_nx_n|=1+2+\dots+n=n(n+1)/2<n^3$, for $n\geq 2$. Then $n^3\nmid \varepsilon_1 x_1 + \varepsilon_2 x_2 + \cdots + \varepsilon_n x_n$. Thus shouldn't all $n$ work? I am surely misunderstanding the problem statement. Please help $\varepsilon_1x_1+\dots+\varepsilon_nx_n$ can be equal to 0, and $n^3 | 0$

Ah...Thanks@sansae and MessingWithMath! That clears my confusion

My solution from WOOT: Assume that $n\ge10$. There are $2^n$ expressions $\sum_{i=1}^n\varepsilon_ix_i$ with $\{\varepsilon_i\}\subseteq\{0,1\}$. Since $2^n>n^3$, the Pigeonhole Principle shows that at least two must have the same remainder$\pmod{n^3}$. Subtracting these, we have an expression in the form $\sum_{i=1}^n\varepsilon_ix_i$ with $\{\varepsilon_i\}\subseteq\{-1,0,1\}$ and $\exists i:\varepsilon_i\ne0$. So $n\le9$. Now we claim that $n=\boxed9$ works. Choose $x_i=2^{i-1}$, and assume that $n^3\mid\sum_{i=1}^n\varepsilon_ix_i$. The maximum of $\sum_{i=1}^n\varepsilon_ix_i$ is $\sum_{i=1}^nx_i=2^n-1<n^3$ while the minimum is $1-2^n>-n^3$. The final case is $\sum_{i=1}^n\varepsilon_ix_i=0$, which we assume. We will prove (by induction) that $\varepsilon_i=0$ for all $i$. First, taking$\pmod2$ gives $\varepsilon_1$ even, so $\varepsilon_1=0$. Now assume that $\varepsilon_i=0$ for all $i<k$ for some $k$. Dividing our equality by $x_{k-1}$ and reading$\pmod2$ gives that $\varepsilon_{k+1}=0$. Since all $\varepsilon_i=0$ after induction, we have a contradiction.

ignore this

ISL 2002/N5 trick strikes again The problem condition is equivalent to $a_1x_1+\cdots+a_nx_n$ being distinct modulo $n^3$ for all $n$-tuples $(a_1,\ldots,a_n)$ whose entries are either $0$ or $1$. Since there are $2^n$ such tuples, we need $2^n \leq n^3 \implies n \leq 9$. For $n=9$, take $(x_1,\ldots,x_9)=(1,2,4,\ldots,256)$. Every combination $a_1x_1+\cdots+a_nx_n$ is a distinct integer between $0$ and $511$, hence all distinct modulo $9^3=729$. $\blacksquare$

Nice PHP: Consider sets $S, T$: $$S = \{ x_i: \epsilon_i = 1 \}, T = \{ x_i: \epsilon_i = -1 \}$$Thus: $$\varepsilon_1 x_1 + \varepsilon_2 x_2 + \cdots + \varepsilon_n x_n \equiv 0 \pmod n^3 \iff \sum S \equiv \sum T \pmod n^3$$ Thus, if we find two different subsets having same sum modulo $n^3$, then it violates the condition. Notice that, there are $2^n$ subsets and $n^3$ resides. Thus, for all $n \ge 10$, $2^n > n^3$ which implies two different subsets have same sum modulo $n^3$ (if they have common elements, remove them and we get disjoint subsets $S, T$ and back-track to get $\epsilon_i$'s) which violates the given condition. We claim that $n = 9$ works. Consider the construction $x_k = 2^{k-1}$ for all $1 \le k \le 9$. The subsets for the set $S = \{ x_1, x_2, \cdots , x_9 \}$ have unique subset sums and they range from $0$ to $2^9-1$. Also, note that: $9^3 > 2^9-1$ which implies no-two (different) subsets have same sum modulo $9^3$ and we are done.