A nice pigeonhole exercise. Consider all sums of the form $\sum_{i=1}^n b_ix_i$ where $b_i \in \{0,1\}$ - they are $2^n$ in number, so if $2^n > n^3$, that is, $n\geq 10$, then there will be two distinct sums with the same remainder modulo $n^3$ and hence their difference will be divisible by $n^3$ and of the form $\sum_{k=1}^n a_kx_k$, $a_k \in \{-1,0,1\}$, contradiction. For $n=9$ take $x_k = 2^{k-1}$, $k=1,\ldots,n$ - then $729$ does not divide any non-zero sum $\sum a_kx^k$, as the latter in modulus does not exceed $2^9 - 1 = 511$.

Romania TST 1996.