Assume $n$ is an even integer. For an odd integer $m$, a sequence of $m$ sets $S_1, \dots, S_m \subseteq [n]$ is a graceful chain of length $m$ if:

  1. $S_1 \subset S_2 \subset \dots \subset S_m$
  2. For every $1 \le i \le m − 1$ we have $|S_{i+1}| = |S_i| + 1$
  3. $|S_m| + |S_1| = n$.

Show that it is possible to decompose the $2^n$ subsets of $[n]$ using $\binom{n}{\frac{n}2}$ graceful chains.

Note: Of course, the chains do not have to be of the same length. Also, recall that by decomposition we mean that each of the $2^n$ sets $S \subseteq [n]$ should appear in exactly one of the graceful chains.

  • 1
    $\begingroup$ What are your thoughts? $\endgroup$ – Zev Chonoles Jun 18 '15 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.