Let $ X_n=\{1,2,...,n\}$,where $ n \geq 3$. We define the measure $ m(X)$ of $ X\subset X_n$ as the sum of its elements.(If $ |X|=0$,then $ m(X)=0$). A set $ X \subset X_n$ is said to be even(resp. odd) if $ m(X)$ is even(resp. odd). (a)Show that the number of even sets equals the number of odd sets. (b)Show that the sum of the measures of the even sets equals the sum of the measures of the odd sets. (c)Compute the sum of the measures of the odd sets.
Problem
Source: Romania TST 1994
Tags: combinatorics proposed, combinatorics
Nukular
28.08.2009 20:30
There's almost certainly a bijective proof, but this might actually be cleaner, and was certainly more straightforward. Let $ g(x) = \prod_{i = 1}^n (1 + x^i)$. Then $ g(x) = \sum_{X \subset X_n} x^{m(X)}$. Then the total number of even sets is the sum of the coefficients of the even part of $ g$, or $ \frac {g(1) + g( - 1)}{2} = \frac {g(1)}{2} = 2^{n - 1}$; since there are $ 2^n$ subsets in total, this is half of the sets. Differentiating, $ g'(x) = \sum_{X \subset X_n} m(X) x^{m(X) - 1}$. The sum of the measures of even sets is the sum of coefficients in the odd part of $ g'$, or $ \frac {g'(1) - g'( - 1)}{2}.$ By the product rule, $ g'(x) = \sum_{i = 1}^n ix^{i - 1} \prod_{j \in [n], i \ne j} (1 + x^j)$. Since $ (1 + x)(1 + x^3) \mid g$, we know $ - 1$ is a double root of $ g$ and is therefore a root of $ g'$. So we have $ \frac {g'(1) - g'( - 1)}{2} = \frac {g'(1)}{2} = (1 + 2 + \dots + n)2^{n - 2} = 2^{n - 2}\binom{n + 1}{2}$. Similarly, the sum of the measures of the odd sets is $ \frac {g'(1) + g'( - 1)}{2} = \frac {g'(1)}{2} = \binom{n + 1}{2}2^{n - 2}$; the two quantities are equal. EDIT: Actually... maybe not. For each $ S \subset X_n$ Pair $ S$ with $ S \oplus \{1\}$ (using $ \oplus$ for symmetric difference). Then this pairing is a bijection between odd and even sets, giving (a). Restricting to sets containing $ \{1\}$, the map $ T \mapsto T \oplus \{3\}$ is a bijection between odd and even sets, so half of all sets containing $ \{1\}$ are even; therefore the sum of the measures of all even sets equals that in all odd sets. Restricting to sets containing $ \{k\}$, for any $ k \ne 1$, the bijection $ S \mapsto S \oplus \{1\}$ takes even sets to odd sets, so every $ k$ is contained in $ 2^{n-2}$ even sets (and $ 2^{n-2}$ odd sets); therefore the sum of the measures of all even (odd) sets is $ (1 + \dots + n)2^{n-2} = \binom{n+1}{2}$.
Albanian Eagle
29.08.2009 03:22
So basically $ g'(-1)=0$ implies b) The total sum of the measures of all subsets of $ X_n$ contains each element $ i$ exactly $ 2^{n-1}=|\mathcal{P}(X_n/\{i\})|$-times. So the total sum is $ 2^{n-1}\binom{n+1}{2}$ so by b) the answer to c) is $ 2^{n-2}\binom{n+1}{2}$
onyqz
30.12.2024 15:55
recursive solution for (b) and (c)
(a)
Consider $P(x)=(1+x)(1+x^2)\cdots(1+x^n)$. Then for each $k=0,\dots,{n+1 \choose 2}$, $[x^k]P(x)=a_k$ gives us the number of subsets with measure equal to $k$.
Note that $\sum_{i=0}^{{n+1\choose 2}}a_i=2^n$. Moreover $\sum_{k\;\text{even}}a_k = \frac{1}{2}(P(1)+P(-1))=2^{n-1}$ (say by roots of unity filter). Therefore also $\sum_{k \;\text{odd}}a_k=2^{n-1}=\sum_{k\;\text{even}}a_k$. $\blacksquare$
(b)+(c)
Let $f(n)$ be the sum of the measures of the even sets and let $g(n)$ be the sum of the measures of the odd sets.
Case 1: $n+1 $ even
Case 1.1: Then $f(n+1)=2f(n)+2^{n-1}(n+1)$, as the even subsets of $n+1$ consist of [all the even subsets of $n$] and [all the even subsets of $n$ for which we also added $\{n+1\}$ since it does not change the parity].
Case 1.2: $g(n+1)=2g(n)+2^{n-1}(n+1)$, as the odd subsets of $n+1$ consist of [all the odd subsets of $n$] and [all the odd subsets of $n$ for which we also added $\{n+1\}$ since it does not change the parity].
Case 2: $n+1$ odd
Case 2.1: Then $f(n+1)=f(n)+g(n)+2^{n-1}(n+1)$, as the even subsets of $n+1$ consist of [all the even subsets of $n$] and [all the odd subsets of $n$ for which we also added $\{n+1\}$ since it changes it's parity].
Case 2.2: $g(n+1)=g(n)+f(n)+2^{n-1}(n+1)$, as the odd subsets of $n+1$ consist of [all the odd subsets of $n$] and [all the odd even of $n$ for which we also added $\{n+1\}$ since it changes it's parity].
We know $f(3)=g(3)=12$ and it follows from induction that $f(n)=g(n)$ for all $n\in \mathbb{Z}^+, n\geq 3$. We will compute $f(n)$ explicitly now:
\begin{align*}
f(n)&=2f(n-1)+2^{n-2}n \\
&= 2(2f(n-2)+2^{n-3}(n-1))+2^{n-2}n = 4f(n-2)+2^{n-2}(n+(n-1)) \\
&= \cdots \\
&= 2^{n-3}f(3)+2^{n-2}\left(\frac{(n+1)(n)}{2}-6\right) \\
&=2^{n-3}(n+1)n \quad \blacksquare
\end{align*}This concludes the problem. $\square$