Prove that any sequence $a_1,...a_n$, $n \geq 5$ contains a subsequence whose elements properly added or subtracted give a multiple of $n^2$

Question

As in the title: Prove that any sequence $a_1,...a_n$, $n \geq 5$ contains a subsequence whose elements properly added or subtracted give a multiple of $n^2$

The idea is probably to use the pigeon principle as was done here For any sequence of $n$ integers, there exists a subsequence whose sum is divisible by $n$.

This situation is however slightly more complicated. I think we can still produce more than $n^2$ different terms, more specifically we have $2$ choices for the sign of each $a_i$ and hence $2^n$ different terms which is greater than $n^2$ for $ n \geq 5 $ . However I don't see how to specifically find a term which is divisible by $n^2$ in this case.

Answer 1

You have $2^n$ different subsequences, and $2^n>n^2$ for $n\ge 5$. So there exist two different subsequences with the same sum modulo $n^2$. Now just take the first minus the second.