wiz-icon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

Let n be a positive integer. Call a non-empty subset S of {1,2,...,n} good, if the arithmetic mean of the elements of S, is also an integer. Further let tn denote the number of good subsets of {1,2,...,n}. Prove that tn and n are both odd or both even.

Open in App
Solution

We show that Tn,n is even.
Note that the subsets {1},{2},,{n} are good.
Among the other good subsets, let A be the collection of subsets with an integer average which belongs to the subset, and let B be the collection of subsets with an integer average which is not a member of the subset.
Then there is a bijection between A and B, because removing the average takes a member of A to a member of B; and including the average in a member of B takes it to its inverse.
So Tnn=|A|+|B| is even.
Alternate solution:
Let S={1,2,...,n}.
For a subset ¯¯¯¯A of S, let A={n+1a|aϵA}.
We call a subset A symmetric if ¯¯¯¯A=A. Note that the arithmetic mean of a symmetric subset is (n+1)/2.
Therefore, if n is even, then there are no symmetric good subsets, while if n is odd then every symmetric subset is good.
If A is a proper good subset of S, then so is ¯¯¯¯A.
Therefore, all the good subsets that are not symmetric can be paired. If n is even then this proves that tn is even.
If n 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 (n+1)/2 if and only if it has odd number of elements.
Therefore, for any natural number k, the number of symmetric subsets of size 2k equals the number of symmetric subsets of size 2k+1.
The result now follows since there is exactly one symmetric subset with only one element.

flag
Suggest Corrections
thumbs-up
0
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Subset
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon