5
$\begingroup$

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

$\endgroup$
6
  • 6
    $\begingroup$ 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. $\endgroup$ Jan 25 at 13:05
  • $\begingroup$ @CraniumClamp Can you explain clearly the solution for me, I can't figure it out. Thanks very much ! $\endgroup$ Jan 25 at 13:11
  • $\begingroup$ $ \{ 1,2,3 \} $ is beautiful, the average is $ 2 $. Remove it, you get $ \{ 1,3 \} $, still beautiful. Take it forward from here? $\endgroup$ Jan 25 at 13:16
  • $\begingroup$ @CraniumClamp I have corrected my comment, can you follow my direction? $\endgroup$ Jan 25 at 14:00
  • $\begingroup$ 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. $\endgroup$ Jan 25 at 14:06

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.