Let $n \geq 2$ be a given integer $a)$ Prove that one can arrange all the subsets of the set $\{1,2... ,n\}$ as a sequence of subsets $A_{1}, A_{2},\cdots , A_{2^{n}}$, such that $|A_{i+1}| = |A_{i}| + 1$ or $|A_{i}| - 1$ where $i = 1,2,3,\cdots , 2^{n}$ and $A_{2^{n} + 1} = A_{1}$ $b)$ Determine all possible values of the sum $\sum \limits_{i = 1}^{2^n} (-1)^{i}S(A_{i})$ where $S(A_{i})$ denotes the sum of all elements in $A_{i}$ and $S(\emptyset) = 0$, for any subset sequence $A_{1},A_{2},\cdots ,A_{2^n}$ satisfying the condition in $a)$
Problem
Source: CWMO 2011 Q3
Tags: floor function, induction, binomial coefficients, graph theory, combinatorics unsolved, combinatorics
22.05.2012 16:19
The funny thing is that I solved b) before a) -_- It's easy to see that the parity of $|A_i|$ always changes as $i$ runs from $1$ to $2^n$. Additionally, for each element $x$, it appears the same number of times in sets of odd cardinality and sets of even cardinality (proof: it appears in $\binom{n-1}{0} + \binom{n-1}{2} + \binom{n-1}{4} + \cdots$ sets of odd cardinality and $\binom{n-1}{1} + \binom{n-1}{3} + \binom{n-1}{5} + \cdots$ sets of even cardinality, which can be proven to be equal with basic binomial coefficients practices). Note the formula basically asks about the difference between the sum of all sets of odd cardinality and the sum of all sets of even cardinality, hence $x$ contributes $0$ to the sum. Summing over all $x$, we have that the formula's value can only be $0$.
22.05.2012 16:41
For a) we use induction. For $n=2$ we can have the sequence $\{1\},\{1,2\},\{2\},\emptyset$. The inductive step I came up with isn't the prettiest and is slightly awkward to explain, nonetheless: Suppose for $\{1,2,3,\ldots ,N\}$ there exists a sequence $(A_i)$ of subsets. We now consider $\{1,2,\ldots ,N+1\}$ and try to construct a sequence $(B_i)$ of subsets $1\le i\le 2^{N+1}$. Now, suppose we "shift" the sequence $(A_i)$ so that $A_{2^N}=\emptyset$ (so that $|A_1|=|A_{2^{N}-1}|=1$ - it's easy to see why we can do this. Now, define \[B_i=\begin{cases}A_i, & \text{if}\ 1\le i\le 2^N\\ A_{i-1}\cup\{N+1\}, & \text{if}\ 2^N+1\le i\le 2^{N+1}\end{cases}\] where $A_{i+2^N}=A_i$. Then this sequence of $B_i$ works. What we've basically done is for the first half of $(B_i)$, we've taken $(A_i)$, which works, then used $A_i$ again but adjoining $N+1$ into each set (so the difference between each set is unaffected). For b), the sum is $0$. Shift the sequence so that $|A_i|=1$. By doing this, we do not change $\left|\sum\limits_{i = 1}^{2^{n}}(-1)^{i}S(A_{i})\right|$, so since it is $0$, we're not actually changing anything. Now, this means $|A_i|$ has the same parity as $i$. Therefore $\sum\limits_{i = 1}^{2^{n}}(-1)^{i}S(A_{i})=\sum_{|S_i|\ \text{even}}^{2^{n}}|S_{i}|-\sum_{|S_i|\ \text{odd}}^{2^{n}-1}|S_{i}|$. Now consider an integer $k$ where $1\le k\le n$. What is $\sum_{|S_i|=k}|S_i|$? Well the number of times an integer $m$ appears in the sets $S_i$ such that $|S_i|=k$ is $\binom{n-1}{k-1}$. So $\sum_{|S_i|=k}|S_i|=\binom{n-1}{k-1}(1+2+\ldots +n)=\binom{n-1}{k-1}\frac{n(n+1)}{2}$. Thus $\sum\limits_{i = 1}^{2^{n}}(-1)^{i}S(A_{i})=\frac{n(n+1)}{2}\left(\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n-1}{2i-1}-\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n-1}{2i}\right)$ (note that we've ignored the empty set in the calculation) But $\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n-1}{2i-1}-\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n-1}{2i}=(1-1)^n$ by binomial expansion, and so we conclude the sum is $0$.
22.05.2012 16:53
This is just the Gray code (wikipedia), isn't it?
12.03.2013 18:49
For part a) you can look at the sets as vertices of a hypercube. Each set can be represented by a string of length $n$ with entries of $0$ and $1$ depending if a specific element is in the set or not. Then, label each vertex of the hypercube such that every 2 are joined by an edge if and only if their strings differ in only one entry. We can prove by induction on $n$ that there is a Hamiltonian cycle on this hypercube. Question: what happens in the countable case? In other words, can we arrange all the finite subsets of the set $\mathbb{N}$ as a sequence of $A_1,A_2, \dots$ such that each set $A_{i+1}$ is formed from $A_i$ by adding or removing one element?