Parity of number of subsets of $\{1,2,3, \ldots, n\}$ whose average value is an integer

Question

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$.

Answer 1

The solution suggested by @Cranium Clamp is by the far the best for your problem.

However, for your inductive argument you wish to count the number of beautiful sets containing both $1$ and $n+1$. The average, $m$, of such a set is neither $1$ nor $n+1$ and these sets can therefore be paired up with two sets being paired if and only if the sets have the form $S$ and $S\cup \{m\}$.

N.B. This of course is the same as @Cranium Clamp's method.

Therefore there is an even number of such beautiful sets.