0

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.

The Lion King
  • 794

1 Answers1

4

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.

TonyK
  • 64,559
  • @CalvinLin: I don't quite see it. Sure, if $n=4$ then either there exist two different subsequences with the same sum, or every residue mod $16$ is represented; and in the second case we can add two subsequences to get a multiple of $16$. But how do we guarantee that these two subsequences have no elements in common? (Or perhaps you had something else in mind?) – TonyK May 27 '23 at 20:04
  • (+1). So say $x= \sum_{n=1}^{n} \alpha_{i,x} a_i$ $y= \sum_{n=1}^{n} \alpha_{i,y} a_i$ with $\alpha_i \in {-1,0,1 }.$ I'm not sure whether the difference can still be built within our rules as for example you might have $\alpha_{1,x}=1$, $\alpha_{1,y} =-1$ and hence $\alpha_{1,x-y}=2 \notin {-1,0,1 } $ – The Lion King May 28 '23 at 07:53
  • @TheLionKing: No, unlike my comment, here $\alpha_i\in{0,1}$. (That's why I said $2^n$ and not $3^n$.) – TonyK May 28 '23 at 10:30
  • @CalvinLin: for a counterexample when $n=4$, take the sequence $(1,2,4,8)$. – TonyK May 28 '23 at 10:34
  • Ah yes, I forgot that the emptyset wasn't a pigeon we could use. Note that in your first line it should be $2^n - 1$ then. – Calvin Lin May 29 '23 at 14:41
  • @CalvinLin: no, I was wrong that the subsets have to be non-empty (when I realised this I changed $2^n-1$ to $2^n$, but forgot to delete the non-empty requirement). If you have a subsequence that adds up to a multiple of $n^2$, then subtracting the empty set is a no-op that leaves you with a subsequence adding up to a multiple of $n^2$, as required – TonyK May 29 '23 at 15:11