• There is a set of $10$ first natural numbers, $S = \{1,2,\cdots,10\}$.
  • Alice picks a subset of it, say $A \subseteq S$.
  • Bob picks a subset of it, say $B \subseteq A$.
  • Charlie picks a subset of it, say $C \subseteq B$.
  • Dave picks a subset of it, say $D \subseteq C$.

How many different ways of their picking are there?
i.e. How many different tuples of $\langle A,B,C,D \rangle$ are there?

  • 1
    $\begingroup$ Subsets, or proper subsets? (i.e. is the null set valid? Is the full set valid?) $\endgroup$ – Chris Cudmore Oct 18 '19 at 13:27
  • 3
    $\begingroup$ is this a math question rather than a puzzle??? $\endgroup$ – Omega Krypton Oct 18 '19 at 13:28
  • $\begingroup$ They are subsets, i.e. it is possible for $A = S$ and also $A = \{\}$. Idk if this is a good puzzle here because I guess the way to solve this is pretty fun as a math puzzle. Tho it's perfectly fine if it's considered off-topic if people say so.. ^^ $\endgroup$ – athin Oct 18 '19 at 13:31
  • $\begingroup$ sorry i have to -1 this as this is off-topic... $\endgroup$ – Omega Krypton Oct 18 '19 at 13:45
  • 6
    $\begingroup$ Seeing the answer, I would consider this a maths puzzle as there is a clever and quick way to solve it which is not immediately obvious. $\endgroup$ – hexomino Oct 18 '19 at 13:51

For each element we can choose the last person to have it in their set. There are $5$ possibilities for each element, namely None, Alice, Bob, Charlie, or Dave. Each element is independent of all the others. Therefore there are $5^{10}=9765625$ ways to arrange the elements amongst the sets.

Here is a nice way to look at it.
Imagine that A chooses some of the 10 items.
B now chooses some of A's items and takes them from her.
C now takes some of B's items from him.
D now takes some of C's items from him.
Any arrangement of the items can be the result. So each item can be with any of the 4 people, or with none of them.
The same is happening in this question, except that the people share the items they took.

| improve this answer | |
  • $\begingroup$ Wow, excellent solution. So much easier to compute than the complex sums of sums of sums... $\endgroup$ – user3294068 Oct 18 '19 at 14:08
  • 1
    $\begingroup$ Indeed, this is how it's done! :) $\endgroup$ – athin Oct 18 '19 at 14:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.