Number of subsets of $U$ whose arithmetic mean is integral

Question

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.

Answer 1

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

Answer 2

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