Let $n\in \mathbb Z^{+}$ and $S_n = \{1,2,3, \ldots, n\}$. A subset $A$ of $S_n$ is said to be beautiful if the average of all the elements in $A$ is an integer.
Let $G_n$ be the set of all beautiful subsets of $S_n$. Prove that $|G_n| \equiv n \bmod 2$.
Here's all I've been able to do:
First, it is easy to see what must be proved true for $n = 1, 2$. I assume the thing to be proved true up to $n =k$; I will prove it also for $n = k+1$.
Thus, I partition the beautiful subsets of $S_n$ into two categories:
Type $1$: Beautiful subsets that do not contain $n+1$. Let $B$ be the number of subsets of type $1$. By the assumption of induction, we get $|B| \equiv n-1 \bmod 2$.
Type $2$: Beautiful subsets that do contain $n+1$. Let the number of subsets of type $2$ be $C$. My idea in this case is:
Let $T$ be the average of any $s$ numbers ($1\le s \le n+1$) that contain $n+1$ (where each number is ${}>1$). I realize that : \begin{align*}T&=\frac{a_1+a_2+a_3+\cdots+a_{s-1}+(n+1)}{s}\\&= \frac{s+(n+1-1)+a_1-1+a_2-1+\cdots+a_{s-1}-1}{s}\\&=s+ \frac{n+(a_1-1)+(a_2-1)+ \cdots +(a_{s-1}-1)}{s}\end{align*} $\Rightarrow T\in \mathbb{Z}$ if and only if the average of $(n,a_1-1,a_2-1,\ldots,a_{s-1}-1)$ is also an integer (because $a_i>1\Rightarrow a_i-1>0$).
Thus we can calculate the number of beautiful subsets of $S_{n+1}$ containing $n+1$ with each element being ${}>1$, which is the number of beautiful subsets of $S_n$ containing $n$.
And Cranium Clamp suggested that if $Q=\frac{b_1+b_2+\cdots+b_{s-1}}{s} \in \mathbb{Z}$, then $\{b_1,b_2,\ldots,b_{s-1},Q\}$ is a beautiful subset.
Thus, the problem that I have not solved is that the sets of type $2$ contain both $(n+1)$ and $1$.