INMO 2013 Problem 4

Let $n$ be a positive integer. Call a nonempty subset $S$ of $\{1,2, \ldots, n\}$ good if the arithmetic mean of the elements of $S$ is also an integer. Further let $t_{n}$ denote the number of good subsets of $\{1,2, \ldots, n\}$. Prove that $t_{n}$ and $n$ are both odd or both even.