1
$\begingroup$

Given a set $\{1,2,3,...,n\}$. Its subset is called a round subset if no-empty and the average of its elements is an integer. Prove that the number of round subsets of the set $\{1,2,3,...,n\}$ has the same parity as $n$.

$\endgroup$
  • 1
    $\begingroup$ Done, now what? $\endgroup$ – barak manos Dec 25 '16 at 5:18
  • $\begingroup$ What do you mean by done? $\endgroup$ – user 42493 Dec 25 '16 at 14:07
  • $\begingroup$ I mean to imply to you that this is not a 'do my homework for free' service, and that you need to show the effort that you've made in attempting to answer this question on your own if you're expecting others to make an effort for you. $\endgroup$ – barak manos Dec 25 '16 at 16:26
1
$\begingroup$

HINT:

  • Show that if $A\subseteq[n]$ is round and has average $m\notin A$, then $A\cup\{m\}$ is round.
  • Show that if $A\subseteq[n]$ is round and has average $m\in A$, then either $A=\{m\}$, or $A\setminus\{m\}$ is round.

Say that a subset of $[n]$ is very round if it is round and has more than one element.

  • Use the first two points to show that $[n]$ has an even number of very round subsets.

  • Combine this with the observation that every $1$-element subset of $[n]=\{1,\ldots,n\}$ is round to get the desired result.

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