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

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

• If a beautiful subset does not contain its average, add it in and you still get a beautiful subset. If a beautiful subset of size bigger than one contains its average, remove it and you still get a beautiful subset. Check that this induces a bijection between beautiful subsets of even size and odd size > 1, let this common number be c. The only ones remaining are the singletons, n of them. So G_n = 2c + n, proving the assertion. Jan 25 at 13:05
• @CraniumClamp Can you explain clearly the solution for me, I can't figure it out. Thanks very much ! Jan 25 at 13:11
• $\{ 1,2,3 \}$ is beautiful, the average is $2$. Remove it, you get $\{ 1,3 \}$, still beautiful. Take it forward from here? Jan 25 at 13:16
• @CraniumClamp I have corrected my comment, can you follow my direction? Jan 25 at 14:00
• I don’t know what you edited but you added my idea that I told you, claiming to be your realization without even a small credit to me. Anyway, I’m done here as I don’t know how to complete your inductive argument. Jan 25 at 14:06

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