Problem:
Let be a positive integer. Call a nonempty subset of good if the arithmetic mean of the elements of is also an integer. Further let denote the number of good subsets of . Prove that and are both odd or both even.
Problem:
Let be a positive integer. Call a nonempty subset of good if the arithmetic mean of the elements of is also an integer. Further let denote the number of good subsets of . Prove that and are both odd or both even.
Solution:
We show that is even. Note that the subsets are good. Among the other good subsets, let be the collection of subsets with an integer average which belongs to the subset, and let be the collection of subsets with an integer average which is not a member of the subset. Then there is a bijection between and , because removing the average takes a member of to a member of ; and including the average in a member of takes it to its inverse. So is even.
Solution:
Let . For a subset of , let . We call a subset symmetric if . Note that the arithmetic mean of a symmetric subset is . Therefore, if is even, then there are no symmetric good subsets, while if is odd then every symmetric subset is good.
If is a proper good subset of , then so is . Therefore, all the good subsets that are not symmetric can be paired. If is even then this proves that is even. If is odd, we have to show that there are odd number of symmetric subsets. For this, we note that a symmetric subset contains the element if and only if it has odd number of elements. Therefore, for any natural number , the number of symmetric subsets of size equals the number of symmetric subsets of size . The result now follows since there is exactly one symmetric subset with only one element.