2
$\begingroup$

Let $n$ and $k$ be two given numbers. The goal is to choose $n$ subsets from $\{1,2,...,n\}$ such that the union of any $k$ of these subsets is the set $\{1,2,...,n\}$ and the union of any $m < k$ of these subsets is not the entire set $\{1,2,...,n\}$.

If $n$ and $k$ are given numbers, then how many ways are there to choose $n$ subsets from $\{1,2,...,n\}$ satisfying the given conditions?

For example, if $n=3$ and $k=2$, there is only one case $(\{1,2\} , \{2,3\} , \{3,1\})$ to choose three subsets from $\{1,2,3\}$ such that every two of these subsets construct $\{1,2,3\}$ and every one of these subsets do not construct the set $\{1,2,3\}$.

It is a kind of secret sharing in the cryptography that we want to distribute $n$ key between $n$ people such that at least we need $k$ people to decrypt.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure why this was closed as off-topic. This question is a natural one to ask in the given context and it does come up every now and then. The answer is folklore and not that hard, but it's not something that I'd expect a random mathematician to come up with immediately, nor am I aware that it is easy to look up. However, I'm not going to vote to re-open since I believe my response answers the question. $\endgroup$ – Timothy Chow Dec 22 '14 at 21:13
  • 1
    $\begingroup$ Professor Chow, I respect to the users who voted to close my post, but for me, your answer to my question was great and constructive and this is essential matter that I have to get from these kind of constructive solutions for my other questions. Thanks so much. $\endgroup$ – Amin235 Dec 22 '14 at 23:24
1
$\begingroup$

Suppose that $\mathscr{F} := \lbrace F_1, \ldots, F_m\rbrace$ is a family of subsets of $X := \lbrace 1, 2, \ldots, n\rbrace$ with the property that the union of any $k$ members of $\mathscr{F}$ is all of $X$ but the union of any $k-1$ members of $\mathscr{F}$ is not all of $X$.

Consider the $m\times n$ 0-1 matrix $M$ whose columns are indexed by the elements of $X$ and whose rows are indexed by members of $\mathscr{F}$ and whose $(i,j)$th entry $M_{i,j}$ is 1 if and only if $j\in F_i$. Then every column has at most $k-1$ zeros, or else taking the union of the $F_i$ corresponding to the zeros in that column would fail to be all of $X$. Similarly, given any $k-1$ rows, there must be a column with zeros in precisely those $k-1$ rows, or else the union of the corresponding $F_i$ would be all of $X$. Thus the only way to construct a matrix with the desired property is to construct one column for each of the $m \choose k-1$ ways to put zeros, and then repeat some columns. In particular, $n\ge {m\choose k-1}$.

You want $m=n$. The only way to achieve $n\ge {m\choose k-1}$ when $m=n$ is if $k=1$, $k=2$, $k=n$, or $k=n+1$. Even if you allow $\mathscr{F}$ to have repeated elements, the case $k=1$ produces only the trivial example in which every $F_i = X$. The case $k=n+1$ does not produce any solutions. The case $k=2$ produces the unique solution that you have already described. Finally, the case $k=n$ produces the unique solution in which each $F_i$ is a distinct singleton set.

$\endgroup$
  • $\begingroup$ First of all, I would like to thank you for taking your time to answer and edit this question. I want to know why $n\geq {m\choose k-1}$ $\endgroup$ – Amin235 Dec 22 '14 at 9:22
  • $\begingroup$ As I said, given any $k-1$ rows, there must be a column with zeros in precisely those $k-1$ rows. There are ${m \choose k-1}$ ways to pick $k-1$ rows out of $m$, so there must be at least ${m\choose k-1}$ columns. By definition, $n$ is the number of columns, so $n\ge {m\choose k-1}$. $\endgroup$ – Timothy Chow Dec 22 '14 at 21:11
  • $\begingroup$ Thank you very much for your very helpful and constructive comments. $\endgroup$ – Amin235 Dec 22 '14 at 22:41

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