Number of subsets of $U$ whose arithmetic mean is integral Question is :-

$n$ is a positive integer. Call a non-empty subset $S$ of $\{1,2,\dots,n\}$ "good" if the arithmetic mean of
  elements of $S$ is also an integer. Further Let $t_n$ denote the number of
  good subsets of $\{1,2,3,\ldots,n\}$. Prove that $t_n$ and $n$ are both odd
  or both even.

And my solution to this problem is :-

We deal with problem in 2 cases : n is even and other when n is odd.
  If n is odd , we first calculate n={1,2} by brute force. We get numbers
  of solutions for n=1 as 1 & n=3 as 5. Thus we conjecture that
  $t_n$=$t_{n-2}+2(n-1)$ for n as even. So by this recurrence we
  calculate $t_5$ which comes to be 15. A brute force manual calculation
  confirms this answer . Thus we prove our conjecture by induction. Now
  $t_1$ is odd (=1) so $t_2$ has to be odd since $t_2$=$t_1+2(3-1)$,here
  $t_1$ is odd & other term is even thus overall parity is odd. So $t_2$
  is odd. Again $t_3$ has to be odd as $t_3$=$t_2$+2(3-1), $t_2$ is odd
  & other term even , so $t_3$ is odd. So , inductively we conclude that
  $t_n$ has to be odd . For the other case we conjecture same recurrence
  relation and prove in the same way.

 A: Let $[n]=\{1,\dots,n\}$. For $S\subseteq[n]$ let $\mu(S)$ be the arithmetic mean of $S$. For $m\in[n]$ let $$\mathscr{S}_m=\big\{S\subseteq[n]:\mu(S)=m\text{ and }S\ne\{m\}\big\}\;.$$ If $m\notin S\in\mathscr{S}_m$, then $S\cup\{m\}\in\mathscr{S}_m$. If $m\in S\in\mathscr{S}_m$, then $S\setminus\{m\}\in\mathscr{S}_m$. Let $$\mathscr{S}_m^*=\{S\in\mathscr{S}_m:m\in S\}\;.$$ Then the map
$$\mathscr{S}_m^*\to\mathscr{S}_m\setminus\mathscr{S}_m^*:S\mapsto S\setminus\{m\}$$
is a bijection, and $|\mathscr{S}_m|$ is even. The good subsets of $[n]$ that do not belong to $\bigcup_{m\in[n]}\mathscr{S}_m$ are precisely the singletons $\{1\},\dots,\{n\}$. If $\mathscr{S}$ is the set of all good subsets, we have
$$|\mathscr{S}|=\left|\bigcup_{m\in[n]}\mathscr{S}_m\right|+n\equiv n\pmod2\;.$$
(This was problem A3 on the 2002 Putnam.)
Added in response to comment: Here’s an example of what’s going on in this proof. Take $n=7$. Then the members of $\mathscr{S}_3$, the subsets of $[7]$ whose average is $3$ (other than the singleton $\{3\}$), are 
$$\begin{align*}
&\{1,5\},\{2,4\},\\
&\{1,2,6\},\{1,3,5\},\{2,3,4\},\\
&\{1,2,3,6\},\{1,2,4,5\},\text{ and}\\
&\{1,2,3,4,5\}\;.
\end{align*}$$
They can be paired up:
$$\begin{align*}
\{1,5\}&\leftrightarrow\{1,\underline{3},5\}\\
\{2,4\}&\leftrightarrow\{2,\underline{3},4\}\\
\{1,2,6\}&\leftrightarrow\{1,2,\underline{3},6\}\\
\{1,2,4,5\}&\leftrightarrow\{1,2,\underline{3},4,5\}
\end{align*}$$
The argument shows that this happens with each collection of subsets all having the same average; that accounts for an even number of good subsets altogether. The only good subsets left are $\{1\},\{2\},\dots,\{7\}$, the same as the original $n$. Thus, we always have $n$ good singletons together with an even number of other good subsets of $[n]$.
A: Let  $A$ be the set of good  subsets of $U=\{1,\ldots,n\}$.
Then 
$$f\colon S=\{a_1,\ldots,a_k\}\mapsto n+1-S=\{n+1-a_k,\ldots,n+1-a_1\}$$
is a bijection $A\to A$ because the average $\overline{f(S)}$ of $f(S)$ is $n+1$ minus the average $\overline S$ of $S$, i.e. if one is integral so is the other. 
Since $f$ is an involution, $A$ can be partitioned into pairs $\{S, f(S)\}$ and the set $A^f$ of fixpoints of $f$. Thus $|A|\equiv |A^f|\pmod 2$.
Buf if $S=f(S)$ is a fixpoint of $f$, then $\overline S=\frac{n+1}2$ because $\overline S=\overline{f(S)}=n+1-\overline S$.
This is integral if and only if $n$ is odd. Hence for $n$ even we have immediately $|A|\equiv|A^f|\equiv 0\pmod 2$.
On the other hand, if $n=2m-1$ is odd, then 
$$g\colon S\mapsto S\Delta\{m\}$$ (symmetric difference) is almost an involutory bijection $A^f\to A^f$: The exception is the one-element set $\{m\}$ that gets mapped to the empty set. In other words, $g$ defines an involution of $A^f\cup\emptyset$. Since $g$ clearly has no fixpoints, we see that $A^f\cup \emptyset$ has an even number of elements, i.e. $|A|\equiv|A^f|\equiv 1\pmod 2$.
