Question

Let $n$ be a positive integer. Call a non-empty subset $S$ of $\{1,2,...,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,...,n\}$. Prove that $t_n$ and $n$ are both odd or both even.

Answer 1

We show that $T_n,n$ is even.
Note that the subsets $\left\{1\right\},\left\{2\right\},,\left\{n\right\}$ are good.
Among the other good subsets, let $A$ be the collection of subsets with an integer average which belongs to the subset, and let $B$ be the collection of subsets with an integer average which is not a member of the subset.
Then there is a bijection between $A$ and $B$, because removing the average takes a member of $A$ to a member of $B$; and including the average in a member of $B$ takes it to its inverse.
So $T_{n}n=|A|+|B|$ is even.
Alternate solution:
Let $S=\{1,2,...,n\}$.
For a subset $\overline{A}$ of $S$, let $A=\{n+1a|aϵA\}$.
We call a subset $A$ symmetric if $\overline{A}=A$. Note that the arithmetic mean of a symmetric subset is $(n+1)/2$.
Therefore, if $n$ is even, then there are no symmetric good subsets, while if $n$ is odd then every symmetric subset is good.
If $A$ is a proper good subset of $S$, then so is $\overline{A}$.
Therefore, all the good subsets that are not symmetric can be paired. If $n$ is even then this proves that tn is even.
If $n$ is odd, we have to show that there are odd number of symmetric subsets. For this, we note that a symmetric subset contains the element $(n+1)/2$ if and only if it has odd number of elements.
Therefore, for any natural number k, the number of symmetric subsets of size $2k$ equals the number of symmetric subsets of size $2k+1$.
The result now follows since there is exactly one symmetric subset with only one element.